Binary Tree Inorder Traversal

The difficult part of inorder traversal is not remembering “left, node, right.” It is preserving the parent node while the left subtree is still unfinished.

The clean solution direction is:

• Recursion stores waiting ancestors in the language call stack.
• Iteration stores those same ancestors in an explicit stack.

Once you see traversal as managing unfinished work, both implementations become the same algorithm with different storage.

Read the traversal contract

The function receives the root of a binary tree and returns a list of node values in inorder:

1. Traverse the entire left subtree.
2. Visit the current node.
3. Traverse the entire right subtree.

That rule applies recursively at every node.

For this tree:

      1
     / \
    2   3
     \ /
      4 5

The traversal is:

[2, 4, 1, 5, 3]

Why?

• The left subtree of 1 produces [2, 4].
• Then we visit 1.
• The right subtree produces [5, 3].

An empty tree has no nodes to visit, so it returns:

[]

One important boundary: inorder output is sorted only when the input is a binary search tree with the required ordering property. An arbitrary binary tree has a defined inorder sequence, but that sequence does not have to be sorted.

Spot the depth-first search signal

This problem gives you the traversal order directly:

left work → current node → right work

That is a depth-first search pattern because each subtree must be completed before control returns to its parent.

The parent node has a specific obligation:

Wait until the left subtree finishes, emit the parent value, then begin the right subtree.

That waiting point is the whole problem.

Compare the three common visit positions:

• Preorder: visit node, then left, then right
• Inorder: left, visit node, then right
• Postorder: left, right, then visit node

Moving the visit operation changes the answer. If you append a value before processing the left child, you have written preorder. If you append it after processing the right child, you have written postorder.

For inorder, the recurrence is:

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

I would start with the recursive version in an interview because it mirrors the contract exactly. Then I would derive the iterative version by asking: what state does recursion remember for us?

Derive the recursive solution

Assume the tree node has the usual interface:

node.val
node.left
node.right

The helper has three jobs:

1. Stop when it receives None.
2. Traverse the left child.
3. Append the current value.
4. Traverse the right child.

The result list is shared output state. The helper does not need to return a new list from every recursive call; it can append values to the one list owned by the outer function.

class Solution:
    def inorderTraversal(self, root):
        result = []

        def dfs(node):
            if node is None:
                return

            dfs(node.left)
            result.append(node.val)
            dfs(node.right)

        dfs(root)
        return result

The call stack supplies the hidden state. When dfs(node) calls dfs(node.left), the current node is not lost. The runtime keeps the parent call suspended, including the fact that it should append the parent value after the left call returns.

That return point matters:

dfs(node.left)
result.append(node.val)

When the left recursive call finishes, execution resumes at result.append(node.val). The parent is now eligible to be visited.

A common incorrect version looks like this:

result.append(node.val)
dfs(node.left)
dfs(node.right)

That emits the node before either subtree, which is preorder. The code can still look like a valid DFS, but it violates the specific contract.

Trace the recursive state

Use the example:

      1
     / \
    2   3
     \ /
      4 5

The recursive execution looks like this:

Current node	Action	Output
1	Descend left	[]
2	No left child; visit 2	[2]
2	Descend right to 4	[2]
4	Visit 4	[2, 4]
1	Left call returned; visit 1	[2, 4, 1]
3	Descend left to 5	[2, 4, 1]
5	Visit 5	[2, 4, 1, 5]
3	Left call returned; visit 3	[2, 4, 1, 5, 3]

Notice what happens at node 1. The function reaches 1, pauses it, explores 2, explores 4, returns from those calls, and only then appends 1.

That is the hidden control flow beginners often lose when they try to write the iterative version.

For an empty tree, the trace is shorter:

dfs(None)
→ return
→ result is []

For a one-sided tree, the same rule still works. A right-only chain such as 1 → 2 → 3 produces [1, 2, 3]. A left-only chain produces [3, 2, 1]. No special case is needed because None is the base case for every missing child.

Turn recursion into an explicit stack

To remove recursion, identify what the call stack was storing.

While descending left, each ancestor is waiting:

• Its left subtree is being explored.
• Its own value has not been emitted yet.
• After it is emitted, its right subtree must be explored.

The explicit stack stores exactly those waiting ancestors.

The iterative algorithm has two phases:

1. While current is a real node, push it and move left.
2. When current is None, pop the next waiting node, visit it, and move to its right child.

class Solution:
    def inorderTraversal(self, root):
        result = []
        stack = []
        current = root

        while current is not None or stack:
            while current is not None:
                stack.append(current)
                current = current.left

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

        return result

Each variable answers a specific obligation:

• current points to the next subtree we should descend into.
• stack holds ancestors whose left work is complete or in progress, but whose values are waiting to be visited.
• result records values in the required order.

The outer loop must continue while either piece of work remains:

while current is not None or stack:

Checking only current is not None would stop too early. After reaching the leftmost leaf, current becomes None, but the stack still contains ancestors waiting to be popped.

Iterative stack trace

For the same tree, the important transitions are:

Step	current action	Stack after action	Output
1	Push 1, move left	[1]	[]
2	Push 2, move left	[1, 2]	[]
3	2.left is None; pop 2, move right	[1]	[2]
4	Push 4, move left	[1, 4]	[2]
5	Pop 4, move right to None	[1]	[2, 4]
6	Pop 1, move right to 3	[]	[2, 4, 1]
7	Push 3, then 5	[3, 5]	[2, 4, 1]
8	Pop 5, move right to None	[3]	[2, 4, 1, 5]
9	Pop 3	[]	[2, 4, 1, 5, 3]

At every pop, the node is ready to visit because its left subtree has already been handled. Its right subtree has not been handled yet, so moving current to node.right preserves the contract.

Iterative invariant: The stack contains waiting ancestors in an order such that the top node is the next node whose left work is complete and whose value can be visited.

The stack is not a generic bag of nodes. It is a record of unfinished obligations.

Prove both versions correct

Recursive version

Use structural induction on the subtree.

• Base case: For node is None, there are no values to return, so the helper does nothing. That is correct.
• Inductive step: Assume the helper correctly traverses both child subtrees. The helper processes the left subtree first, appends the current node, and processes the right subtree second. Therefore it produces exactly left-node-right order for the current subtree.

Since the root call applies this rule to the whole tree, the result is correct.

Iterative version

Maintain the stack invariant described above.

When the algorithm pushes a node, it is moving left before visiting that node. Therefore the node cannot be popped until the traversal has finished descending through its left side.

When the algorithm pops a node:

1. Its left subtree has already been processed.
2. Its value is appended next.
3. current moves to its right subtree, which is processed afterward.

So every pop respects left-node-right order.

Each node is pushed once and popped once. A node is appended exactly when it is popped, so no node is omitted or visited twice.

Complexity, edge cases, and checks

Let n be the number of nodes and h the tree height.

Time

Both versions run in:

O(n)

The recursive version executes one helper call per node, plus calls for missing children. The iterative version pushes and pops each real node once. There is no repeated subtree traversal.

Space

The output list requires:

O(n)

That is required to return all node values.

The auxiliary traversal space is:

O(h)

• Recursion uses the call stack.
• Iteration uses the explicit stack.

A balanced tree has smaller maximum depth than a one-sided chain with the same number of nodes. The shape of the tree controls how many ancestors can be waiting at once.

The iterative version makes that memory visible and avoids relying on recursive calls. The recursive version is shorter and usually easier to explain. My practical rule is simple: use recursion when the contract-to-code mapping is the clearest answer; use the explicit stack when the interviewer asks for iteration or when you want direct control over traversal state.

Edge-case checks

Run these cases before trusting the implementation:

Tree shape	Expected behavior
Empty tree	Return []
One node	Return [value]
Left-only chain	Values appear from deepest left node back toward the root
Right-only chain	Values appear from root toward the deepest right node
Both children	Left values, root value, then right values
Repeated values	Preserve every occurrence; do not deduplicate
Any shape	Return values, not node objects, and do not modify links

These tests target the actual failure points: missing base cases, incorrect visit timing, and losing pending ancestors.

The transferable pattern

When the required order is:

left work → node work → right work

ask what must wait between the two subtree operations.

Recursion stores that waiting parent implicitly in the call stack. Iteration stores it visibly in a stack while a pointer walks left.

That is the reusable recognition rule. Do not memorize the loop as a trick. Track the unfinished obligation: every node is visited after its left work and before its right work. Test the empty tree and one-sided trees first, then verify that the state still obeys that rule at every step.