Tree traversals

Why it costs this much

Every node is visited exactly once, and the recursion stack holds only one root-to-node path.

Code

def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)        # each node is appended once: O(n)
        inorder(node.right, out)    # stack depth never exceeds the height h

Common pitfalls

Space is O(h), which is O(n) on a skewed tree. Level-order traversal uses O(w) space for the widest level w.

Operation by operation

Tree traversal (in-order, pre-order, post-order, level-order). Visits each node once. h is height, w is the widest level. A skewed tree has h = n, so the recursion stack is O(n).