Binary Tree Inorder Traversal — Editorial

Opening the reading…

Intuitionhow the stack remembers where recursion would return

Inorder traversal has one exact order: finish the left subtree, visit the node, then finish the right subtree. When recursion visits a node, it quietly remembers that node while it travels left, then returns to it after the left side is done. The iterative solution must make that hidden memory explicit.

Start at the root and push every node on the path to the leftmost node. The top of the stack is then the next node whose left subtree is complete, so pop it, record its value, and continue from its right child. If that right child exists, its entire left path becomes the next work to push. The stack therefore contains exactly the ancestors that are waiting for their turn.

Approachturning the recursive return points into explicit stack entries

Create an empty result vector, a stack of tree nodes, and set curr to the root, because the result needs one shared destination and the stack must remember unfinished ancestors.

Continue while curr exists or the stack is not empty, because either condition means there is still a node to descend into or a node waiting to be processed.

Push curr and move to curr->left repeatedly, because every node on this path must be visited only after its left subtree has been completed.

When curr is null, pop the stack top, because the popped node is the first waiting ancestor whose left side is finished.

Append the popped node's value to the result, because inorder visits the root between its left and right subtrees.

Move curr to the popped node's right child, because that is the only subtree still unvisited for that node; if it is null, the next loop iteration pops another waiting ancestor.

Return the result after both curr is null and the stack is empty, because those two facts together prove that every reachable node has been processed.

Complexitythe stack stores one unfinished path, not every node

MEASURE	BOUND	WHY
Time	O(n)	Each node is pushed once, popped once, and appended once. Moving left or right only advances through an edge or processes a node, so no node or edge is revisited by a second traversal.
Space	O(h) extra space	The result vector is required output and is excluded. The stack contains only the current root-to-leaf path and waiting ancestors, so it uses O(h); this is O(log n) for a balanced tree and degrades to O(n) for a completely one-sided tree.

Here n is the number of nodes and h is the tree height, measured as the maximum number of nodes on a root-to-leaf path.

Annotated solutionC++ · iterative stack traversal · left, root, right

CPPThe stack-based implementation that simulates recursive inorder traversal.

#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* curr = root;

        while (curr != nullptr || !stk.empty()) {
            while (curr != nullptr) {
                stk.push(curr);
                curr = curr->left;
            }

            curr = stk.top();
            stk.pop();
            res.push_back(curr->val);
            curr = curr->right;
        }

        return res;
    }
};

The outer loop uses an OR, not an AND. After the left descent reaches null, curr is empty but the stack still contains ancestors to process. After popping a node, assigning curr to its right child either starts another descent or leaves the stack to supply the next ancestor. Those two assignments are what connect separate left paths into one continuous traversal.