LeetCode 94 – Binary Tree Inorder Traversal

Binary Tree Inorder Traversal is four lines recursively, which is why the problem statement ends with "could you do it iteratively?" — the recursion is the warm-up and the explicit stack is the question. It is worth doing properly because the iterative form is the skeleton behind BST iterators, and because inorder on a BST has a property the next problem depends on.

The problem

Given the root of a binary tree, return the inorder traversal of its node values: left subtree, then the node, then the right subtree.

    1
     \          -> [1, 3, 2]
      2
     /
    3

[]        -> []
[1]       -> [1]

    4
   / \        -> [1, 2, 3, 4, 5, 6, 7]
  2   6
 / \ / \
1  3 5  7

That last one is a binary search tree, and the output is sorted. That is not a coincidence and it is the single most useful fact about inorder traversal: inorder on a BST visits values in ascending order. The next problem is built on it.

Recursive

inorder(node):
    inorder(node.left)
    visit(node)
    inorder(node.right)

Preorder, inorder and postorder differ only in where visit sits among those three lines. Say that — it shows the three are one algorithm rather than three to memorise.

    private void walk(TreeNode node, List<Integer> out) {
        if (node == null) return;
        walk(node.left, out);
        out.add(node.val);
        walk(node.right, out);
    }

Correct, and O(h) stack where h is the height. On a degenerate tree — a linked list of ten thousand nodes, which is what you get from inserting sorted data into an unbalanced BST — that overflows. This is the real reason the iterative version is asked for, and a better answer than "they wanted to see if I could".

The iterative version

Make the call stack explicit. The rule: go left as far as possible, pushing as you go; then pop, visit, and turn right.

    4
   / \
  2   6        push 4, push 2, push 1     stack [4,2,1]
 / \ / \       pop 1, visit, right=null   -> [1]
1  3 5  7      pop 2, visit, go right(3)  -> [1,2]   push 3
               pop 3, visit               -> [1,2,3]
               pop 4, visit, go right(6)  -> [1,2,3,4]  push 6, push 5
               ...

The loop condition is the part that trips people: current != null || !stack.isEmpty(). Both halves are needed. After visiting a node with no right child, current is null but there are still ancestors waiting; after turning right, current is non-null but the stack may be empty. Testing only one ends the traversal early.

Java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;

        // current != null: there is a subtree still to descend into.
        // stack non-empty: there are ancestors still waiting to be visited.
        while (current != null || !stack.isEmpty()) {
            while (current != null) {        // go left as far as it goes
                stack.push(current);
                current = current.left;
            }

            current = stack.pop();
            out.add(current.val);            // left subtree is done -- visit
            current = current.right;         // now the right subtree
        }

        return out;
    }
}

ArrayDeque rather than Stack, for the reason Simplify Path goes into — and note that ArrayDeque rejects null elements, which here is a feature: it turns "I pushed a null child by mistake" into an immediate exception instead of a confusing traversal.

There is no visited flag anywhere. The structure of the loop guarantees a node is popped only once its entire left subtree has been consumed, which is what makes the traversal correct without extra state.

Python

class Solution:
    def inorderTraversal(self, root: TreeNode) -> list[int]:
        out: list[int] = []
        stack: list[TreeNode] = []
        current = root

        while current or stack:
            while current:                  # descend left, remembering the way back
                stack.append(current)
                current = current.left

            current = stack.pop()
            out.append(current.val)
            current = current.right

        return out

while current or stack reads as the invariant directly: keep going while there is something to descend into or something to come back to.

Morris traversal: O(1) space

If asked for constant space — no stack, no recursion — the answer is Morris traversal. It uses the tree's own null right pointers as temporary links back to the ancestor, then removes them:

    def inorderMorris(self, root: TreeNode) -> list[int]:
        out, current = [], root

        while current:
            if current.left is None:
                out.append(current.val)
                current = current.right
            else:
                # Rightmost node of the left subtree: the one visited just before `current`.
                predecessor = current.left
                while predecessor.right and predecessor.right is not current:
                    predecessor = predecessor.right

                if predecessor.right is None:
                    predecessor.right = current      # thread: a way back up
                    current = current.left
                else:
                    predecessor.right = None         # unthread: restore the tree
                    out.append(current.val)
                    current = current.right

        return out

Two things to say about it rather than just producing it. It is still O(n) time despite the inner loop, because each edge is walked at most twice. And it mutates the tree during traversal — it restores everything by the end, but the tree is temporarily malformed, which rules it out if anything else might be reading concurrently.

Offer it when constant space is asked for. Leading with it is showing off, and if you cannot explain the threading you should not open with it.

Complexity

Approach	Time	Space
Recursive	`O(n)`	`O(h)` stack — `O(n)` if degenerate
Explicit stack	`O(n)`	`O(h)`
Morris	`O(n)`	`O(1)`

O(h) is O(log n) on a balanced tree and O(n) on a degenerate one. Excluding the output list, which is O(n) for all three.

The pattern

The explicit-stack version is the body of a BST Iterator (173): keep the descend-left loop as the "advance" step and the traversal becomes lazy, yielding one value per next() call in O(1) amortised time and O(h) space. That is the same code split across two methods, and recognising it is worth more than either problem alone.

Validate BST (98) uses the sorted-output property directly. Kth Smallest Element in a BST (230) is inorder with an early exit at the kth value. Preorder (144) and postorder (145) have their own iterative forms; preorder is easier than this one, postorder harder.

What the interviewer is checking

That you give the recursion, then convert it without being asked twice.
The loop condition current != null || !stack.isEmpty(), and why both halves.
That the recursive stack depth is O(h), and what a degenerate tree does to it.
Empty tree and single node.
That inorder on a BST is sorted.
That no visited flag is needed, and why.
Bonus: Morris, and that it temporarily mutates the tree.