Binary Tree Inorder Traversal

Problem

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

Follow up: Recursive solution is trivial, could you do it iteratively?

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution

The problem Binary Tree Inorder Traversal can be solved using a stack to store nodes. By traversing through the node to the left and pushing it to the stack until no node exists, it can be guaranteed that the top of the stack contains a node that either does not have nodes on the left or all nodes on its left are already processed.

Implementation

typedef stack<TreeNode *> Stack;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  public:
    vector<int> inorderTraversal(TreeNode *root)
    {
        vector<int> ret;
        Stack roots;

        while (!(root == NULL && roots.empty()))
        {
            while (root != NULL)
            {
                roots.push(root);
                root = root->left;
            }

            root = roots.top();
            roots.pop();
            ret.push_back(root->val);
            root = root->right;
        }

        return ret;
    }
};