Traversal families

Three of the four tree traversals are the same function. The recursion is identical — descend left, descend right — and the only thing that changes is where the line that touches the node sits relative to those two calls. Put it before both and you have preorder, between them and you have inorder, after both and you have postorder.

That is not a mnemonic. It is the reason each order is good at a different job, because the position of the visit decides what is already known when it runs.

One recursion, three visit positions

def walk(node, out):
    if node is None:
        return
    # out.append(node.val)      # preorder:  nothing below is known yet
    walk(node.left, out)
    # out.append(node.val)      # inorder:   the left subtree is done
    walk(node.right, out)
    # out.append(node.val)      # postorder: both subtrees are done

Uncomment exactly one of those lines. Every node is reached once and each call site fires once per node, so all three run in O(n) time. The space is the recursion stack, O(h) where h is the height — 20 frames on a balanced tree of a million nodes, because 2²⁰ = 1,048,576, and a million frames on a tree that has degenerated into a chain. That gap is the subject of the BST invariant.

A seven-node binary tree with its preorder, inorder and postorder sequences listed beneath it100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

What each order is for

Preorder emits a parent before its children, so a consumer can create a node before it has anywhere to hang the children it has not seen yet. Deep copy, serialisation, and printing a directory tree are all preorder for that reason: the receiver can allocate as it reads, top down, with no buffering.

Inorder on a binary search tree emits keys in sorted order. Read the middle row of the diagram — A B D E F G I — and note that no comparison was involved; the sortedness is a property of the shape. Everything that wants BST keys in order rides on this: kth-smallest, checking a tree is a valid BST by confirming the walk is strictly increasing, and range queries that stop early.

Postorder gives a node both children's answers before it runs. Height, subtree sums, "delete the whole tree" (free the children before the parent, or you have lost the pointers), and nearly every problem in structure and paths sit here. When a node cannot answer without asking below first, the visit belongs after both calls.

Choosing the order is usually the whole design decision. If you can say "this node needs its children's results", you have said postorder, and the code writes itself.

Level order, one level at a time

Level order is not a variation on the recursion — it needs a queue, because the next node to visit is the oldest one discovered, not the deepest.

The version people usually want is grouped by level, and the trick is one line: take the queue's length before the inner loop and treat that as the width of the current level.

from collections import deque

def levels(root):
    if root is None:
        return []
    out, q = [], deque([root])
    while q:
        width = len(q)            # this level, frozen before we add to it
        row = []
        for _ in range(width):
            node = q.popleft()
            row.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        out.append(row)
    return out

The mistake is an inner loop that reads the queue live — while q: where the fixed width belongs. It does not hang: range(len(q)) evaluates the length once, and even the Java form for (int i = 0; i < q.size(); i++) stops when the queue drains. What the live read loses is the boundary. The appends feed the same inner loop, so it keeps going until the tree is exhausted and every remaining node ends up in one row. On the tree above, [[F], [B, G], [A, D, I], [E]] collapses to a single row of all seven nodes: still a correct level-order sequence, with the four levels thrown away. Freezing the width first is what separates them.

Space is the widest level, not the height, and for a full tree the bottom level holds about half of all nodes. A balanced million-node tree therefore peaks at roughly 500,000 queued references — about 4 MB at 8 bytes each — against 20 stack frames for a depth-first walk of the same tree. Level order is the one traversal whose memory you should quote in nodes rather than in height.

Iterative inorder, and why you would bother

CPython's default recursion limit is 1000 frames. A tree of 100,000 nodes built by inserting sorted keys is a chain of height 100,000, so the recursive walk dies with a RecursionError about 1% of the way in. Raising the limit trades a clean exception for a dirty one: the C stack is typically 8 MB and a Python frame costs a few hundred bytes, so somewhere in the tens of thousands of frames the process stops raising and starts crashing.

An explicit stack moves that storage onto the heap, where there is room:

def inorder(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:               # go left, remembering the way back
            stack.append(node)
            node = node.left
        node = stack.pop()        # leftmost node not yet emitted
        out.append(node.val)
        node = node.right         # then everything to its right
    return out

At most h references sit in the list, 8 bytes each, so 100,000 deep costs about 800 KB and no interpreter limit applies. Learn this loop in exactly this shape — push while descending left, pop to visit, step right — because a BST iterator that yields "the next key in sorted order" on demand is this loop paused between the pop and the step right, with O(h) memory instead of O(n).

In an interview

State the order you are using and why, in the same sentence: "postorder, because each node needs its children's heights before it can compute its own." That one line tells the interviewer you chose rather than defaulted, and it is the same move as naming the waste in the solving loop.

Say the recursion depth out loud when the input can be adversarial. "Recursive inorder is O(h) stack, and h can be n if the tree is a chain, so with n up to 10⁵ I will use an explicit stack" is a sentence that gets you credit for a failure mode most candidates never mention.

The mistake that loses points: writing the inner loop as while q: and handing back one flat row where the interviewer asked for rows per level. It terminates and it visits every node, so nothing crashes and the bug survives a quick trace — the levels are simply gone. Snapshot the width; it is one line and it is the entire correctness argument for the grouping.

Check yourself

You need to serialise a tree to a string and rebuild the same shape from it. Which traversal do you emit, and why not inorder?

Preorder, with explicit markers for null children. The root arrives first, so the reader can build a node before it has children. Inorder alone does not determine the shape at all — many different trees share one inorder sequence.

A balanced tree holds 10⁶ nodes. Compare the peak memory of a recursive depth-first walk with a level-order walk.

Depth-first peaks at the height: log₂(10⁶) ≈ 20 stack frames. Level order peaks at the widest level, about 500,000 references, roughly 4 MB at 8 bytes each — four orders of magnitude more, for a traversal that visits the same nodes.

The input is 10⁵ keys inserted in increasing order into an unbalanced BST, and you want them printed in sorted order. What breaks, and what do you write?

Sorted inserts make a chain of height 10⁵, so recursive inorder blows the 1000-frame limit almost immediately. Write the iterative inorder with an explicit stack: about 800 KB of heap, still O(n) time.