Tree traversal orders

This is usually taught as three recursive functions that look almost identical, which makes them easy to write and impossible to remember. They are easier to hold on to as a single question: at what point do you deal with the node itself — before its children, between them, or after both? Walk each one and watch the output build.

Why in-order comes out sorted#

Only on a binary search tree, and only because of the invariant that put it there: everything in the left subtree is smaller than the node, everything in the right subtree is larger. In-order says finish the smaller things, take me, then do the larger things, which is the definition of ascending order applied recursively — watch that invariant hold as you insert values yourself in the binary search tree visualiser.

This is the reason a database index can answer ORDER BY without sorting anything. The order was decided when the data went in, and reading it out in the right sequence is free.

Level order is the odd one out#

The other three are depth-first and get their bookkeeping for free from the call stack. Level order is breadth-first: you need a queue, and you have to manage it yourself. If you find yourself trying to write level order recursively, that is the reason it will not come out.

def in_order(node, out):
    if node is None:
        return out
    in_order(node.left, out)      # everything smaller
    out.append(node.value)        # then me
    in_order(node.right, out)     # then everything larger
    return out

def level_order(root):
    # the one order the call stack cannot give you
    out, queue = [], [root]
    while queue:
        node = queue.pop(0)
        out.append(node.value)
        queue += [c for c in (node.left, node.right) if c]
    return out

Both are seven lines of code. The difference that matters is not the recursion — it is pop(0) versus the stack: taking from the front gives you rows, taking from the back gives you branches, at the O(n) cost of shifting a plain list that a deque would not pay.

Start from what you want out#

Whichever row you land on, the number of nodes visited is the same n. What differs is the bookkeeping — and for the three depth-first orders that bookkeeping is O(h) stack frames deep, where h is the height. Height is not something a traversal decides; it was settled earlier, by the order the values arrived in. Insert values in sorted order in the AVL tree visualiser and watch a plain search tree collapse into a list while an AVL tree beside it rotates to keep its height near log n — which is what makes that O(h) worth knowing the size of, and where this path goes next.

Where it goes wrong#

Why in-order comes out ascending, above, turns on the invariant rather than on the traversal. That cuts the other way too. In-order does not check the invariant — it walks left, visits the node, walks right, on any binary tree, valid or not. When the invariant breaks, nothing about the walk changes; only the output does. It runs to completion and returns something that is nearly sorted, not sorted — which is harder to notice than a result that looks obviously wrong.

Mixed conventions for duplicate keys are the near miss, and they are worth ruling out first. Equal keys can legitimately go left or right of an existing match, and both conventions keep everything on the left no larger and everything on the right no smaller — so a tree built by mixing them still walks out sorted. What mixing breaks is lookup: a search for a duplicate descends one way while the matching key sits the other, and the tree quietly reports a value it holds as absent. Reading the output will never show you that.

The invariant also breaks when a node is edited in place. Changing the value stored at a node, rather than removing that node and reinserting the new value, leaves every left and right pointer exactly where it was — the shape stays intact — while the value sitting at that position may no longer belong there. No insert or delete runs afterward to catch this, because none happened, and nothing checks it on read, because in-order does not check — it reads what is there and reports it.

That gap is worth closing with a test rather than a read-through of the output. Walking a tree in-order and confirming the values never decrease is a cheap check to have standing in a test suite, and it is precise where staring at output is not — it turns “this looks almost sorted” into a failing assertion at the exact pair of values where the invariant gave out.

def is_sorted(node):
    values = in_order(node, [])
    return all(a <= b for a, b in zip(values, values[1:]))