Home
How to Do Binary Tree Inorder Traversal in C/C++?
Tags:, , , ,

How to Do Binary Tree Inorder Traversal in C/C++?

April 16, 2016 No Comments algorithms, c / c++, data structure, leetcode online judge, programming languages

Given a binary tree, return its inorder traversal of its nodes’ values.

For example:
The binary tree,

   1
    \
     2
    /
   3

should return the inorder = [1,3,2].

Recursion

Recursion is trivial and should be easy to implement. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        vector<int> x;
        if (root->left != NULL) {
            x = inorderTraversal(root->left);
            r.insert(r.end(), x.begin(), x.end());
        }
        r.push_back(root->val);
        if (root->right != NULL) {
            x = inorderTraversal(root->right);
            r.insert(r.end(), x.begin(), x.end());
        }
        return r;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        vector<int> x;
        if (root->left != NULL) {
            x = inorderTraversal(root->left);
            r.insert(r.end(), x.begin(), x.end());
        }
        r.push_back(root->val);
        if (root->right != NULL) {
            x = inorderTraversal(root->right);
            r.insert(r.end(), x.begin(), x.end());
        }
        return r;
    }
};

The recursive idea is to visit the left sub trees first, and visit the parent node, and last visit the right sub trees. We should append the results of vector using STL::insert that takes 3 parameters.

We can also make it concise without checking the nullibility of the left and right sub trees and re-arrange the code a little bit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> ans = inorderTraversal(root->left);
        ans.push_back(root->val);
        auto right = inorderTraversal(root->right);
        ans.insert(end(ans), begin(right), end(right));
        return ans;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> ans = inorderTraversal(root->left);
        ans.push_back(root->val);
        auto right = inorderTraversal(root->right);
        ans.insert(end(ans), begin(right), end(right));
        return ans;
    }
};

Iterative

We can use a stack to emulate the recursion. We first push the left nodes as many as possible, if not, we push the right sub trees. This gives an inorder traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        stack<TreeNode*> st;
        TreeNode* p = root;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            p = st.top();
            st.pop();
            r.push_back(p->val);
            p = p->right;
        }
        return r;
    }
};
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        stack<TreeNode*> st;
        TreeNode* p = root;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            p = st.top();
            st.pop();
            r.push_back(p->val);
            p = p->right;
        }
        return r;
    }
};

If you don’t like nested while loop, we can slightly rewrite the above, but using the same idea:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        stack<TreeNode*> st;
        TreeNode* p = root;
        while (p || !st.empty()) {
            if (p) {
                st.push(p);
                p = p->left;
            } else {
                p = st.top();
                st.pop();
                r.push_back(p->val);
                p = p->right;
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        stack<TreeNode*> st;
        TreeNode* p = root;
        while (p || !st.empty()) {
            if (p) {
                st.push(p);
                p = p->left;
            } else {
                p = st.top();
                st.pop();
                r.push_back(p->val);
                p = p->right;
            }
        }
        return r;
    }
};

The above two approaches push the left nodes into the stack, but never right sub trees, instead, it uses another pointer to navigate to the right sub trees. If we push every node into the stack, we need to avoid pushing the same node into the stack twice.

We can use map, unordered_map, set or unordered_set to remember the visited Nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        stack<TreeNode*> st;
        st.push(root);
        unordered_set<TreeNode*> visited;
        while (!st.empty()) {
            auto p = st.top();
            if (p->left != NULL && (!visited.count(p))) {
                st.push(p->left); // push left nodes
                visited.insert(p); // remember the node
            } else {
                st.pop();
                r.push_back(p->val);
                if (p->right != NULL) {
                    st.push(p->right); // push right nodes
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        if (root == NULL) {
            return r;
        }
        stack<TreeNode*> st;
        st.push(root);
        unordered_set<TreeNode*> visited;
        while (!st.empty()) {
            auto p = st.top();
            if (p->left != NULL && (!visited.count(p))) {
                st.push(p->left); // push left nodes
                visited.insert(p); // remember the node
            } else {
                st.pop();
                r.push_back(p->val);
                if (p->right != NULL) {
                    st.push(p->right); // push right nodes
                }
            }
        }
        return r;
    }
};

Which method do you like best? Comment below 🙂

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
684 words
Last Post: C/C++ Coding Exercise - Path Sum for Binary Tree
Next Post: How to Get All Binary Tree Paths in C/C++?

The Permanent URL is: How to Do Binary Tree Inorder Traversal in C/C++?

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  3. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  4. Three ways of Running a continuous NodeJS Application on Your Server Let’s say, I have an application that is written in NodeJs, that process the latest...
  5. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  6. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  7. How to Find the Kth Smallest Element in a BST Tree Using Java/C++? Given a binary search tree, write a function kthSmallest to find the kth smallest element...
  8. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...

Leave a Reply