Skip to content

Inorder traversal

Problem

Return a binary tree's values in inorder: left subtree, node, then right subtree. Implement both recursive and iterative versions.

Tree:        2
            / \
           1   3

Input:  root = [2, 1, 3]
Output: [1, 2, 3]

Key trick

The iterative version uses a stack to simulate recursive calls: push the entire left path, visit the top node, then move to its right subtree.

Trap

  • Visiting a node when first encountered instead of after its left subtree.
  • Forgetting to process the right subtree.
  • Using a mutable default accumulator in the recursive version.
  • Ignoring that recursion can exceed Python's recursion limit on a deeply skewed tree.

Why is it interesting?

It demonstrates how an implicit recursive call stack can be converted into an explicit stack.

Python solution

from utils import TreeNode


def inorder_recursive(root: TreeNode | None) -> list[int]:
    res = []

    def dfs(node: TreeNode | None) -> None:
        if node is None:
            return

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

    dfs(root)
    return res


def inorder_iterative(root: TreeNode | None) -> list[int]:
    res = []
    stack = []
    cur = root

    while cur or stack:
        # Delay visiting each node until its left subtree is complete.
        while cur:
            stack.append(cur)
            cur = cur.left

        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right

    return res
  • Time: \(O(n)\) for both versions.
  • Auxiliary space: \(O(h)\) for both versions, where \(h\) is the tree height; \(O(n)\) in the worst case.
  • Output space: \(O(n)\).