Tree Traversal: Why the Order You Pick Is a Data Flow Decision

Tree traversal usually gets taught as three separate algorithms to memorize: preorder, inorder, postorder. They are not three algorithms. They are one recursive function with a single line moved to a different spot, and that one line decides which problems you can solve.

I watched this trip up people prepping for months. They had all four traces memorized and still froze when a new problem asked them to pick an order. The trace is the easy part. Knowing which order hands you the information you need is the part that actually matters in an interview.

TL;DR: Traversal visits every node once. The four standard orders differ only in when the current node gets processed relative to its children. Preorder processes the node before its children, postorder after, inorder between, and level order goes breadth first with a queue. Pick the order by asking which direction data has to move between a parent and its children.

The four orders on one tree

Run all four on the same tree and the difference stops being abstract.

Preorder (node, left, right): 1, 2, 4, 7, 5, 3, 6
Inorder (left, node, right): 7, 4, 2, 5, 1, 3, 6
Postorder (left, right, node): 7, 4, 5, 2, 6, 3, 1
Level order (breadth first): 1, 2, 3, 4, 5, 6, 7

Inorder looks unsorted here because this is not a binary search tree. The sorted property only shows up when the values obey the BST invariant of left less than node less than right. On a plain binary tree, inorder still walks left, node, right, but the numbers come out in whatever order the structure gives you.

The only thing that changes is one line

The three depth first orders are the same code. The recursive call structure is identical. The only difference is where the line that processes the node sits relative to the two recursive calls.

def preorder(node):
    if not node:
        return
    process(node)        # before the children
    preorder(node.left)
    preorder(node.right)

def inorder(node):
    if not node:
        return
    inorder(node.left)
    process(node)        # between the children
    inorder(node.right)

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    process(node)        # after the children

Move one line, change the order. That is the whole trick for the depth first family.

Why postorder is the one that computes heights

This is where order stops being trivia. Take the height of a binary tree. To know a node's height, you need the heights of both children first. You take the larger child height and add one. That dependency, children before parent, is exactly what postorder gives you.

def height(node):
    if not node:
        return -1            # an empty subtree has height -1
    left = height(node.left)
    right = height(node.right)
    return max(left, right) + 1

Trace it on the tree above and watch every node wait for its children before it can answer.

Node 7: leaf                      -> 0
Node 4: left(7)=0, no right       -> max(0, -1) + 1 = 1
Node 5: leaf                      -> 0
Node 2: left(4)=1, right(5)=0     -> max(1, 0) + 1 = 2
Node 6: leaf                      -> 0
Node 3: no left, right(6)=0       -> max(-1, 0) + 1 = 1
Node 1: left(2)=2, right(3)=1     -> max(2, 1) + 1 = 3

Try the same thing with preorder and you hit the parent first, with no information about the subtree below it. You can still make it work by passing depth down as a parameter and tracking a maximum in an outer variable, but it is fifteen awkward lines where postorder is five. Diameter, subtree sums, balanced checks, distributing coins: same shape every time. The parent cannot answer until both children have reported back, so you process the children first.

The first time I had to write any of these iteratively under a timer, I realized I had memorized the recursion and never the stack sitting under it. That gap is part of why I built Codeintuition, and the binary tree course traces the stack state for the iterative versions one frame at a time.

Level order is the odd one out

Level order is the only one that is not depth first. It uses a queue, not the call stack. Enqueue the root, then repeatedly dequeue a node and enqueue its children. Nodes come out one full level at a time.

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        process(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Anything that works on nodes at the same depth (level sums, zigzag traversal, connecting nodes across a level) needs this breadth first access. Forcing depth first to do the same job means tracking depth by hand, which is more bookkeeping than the problem deserves.

Picking the order: which way does the data flow?

Almost every tree problem opens with the same hidden question. Does the parent need answers from its children, or do the children need data handed down from the parent? Answer that and the order falls out.

Postorder: the parent needs results from both children (height, diameter, subtree sums, balanced checks)
Preorder: the children need data passed down from the parent (root to leaf path sums, serialization)
Inorder: you want values in sorted order out of a BST
Level order: the work happens per level (level sums, zigzag, connecting same depth nodes)

A quick aside worth its own paragraph: there is a real argument that some problems read fine in more than one order, and reconstructing a tree from traversals is its own rabbit hole (preorder alone is not enough, you need inorder too, or null markers). That is a separate post. For the day to day of picking an order on sight, the data direction question settles it.

Listing the four orders is the easy part of this topic. Looking at an unfamiliar tree problem and knowing which order hands you the right information before you write a line is the skill that actually transfers to an interview, and it comes from understanding why each order exists, not from re-reading the traces.

I wrote a longer version on my own blog that walks through the iterative conversions for all three depth first orders.

Which traversal order was the one that finally made sense to you only after you got burned picking the wrong one on a real problem?

推荐订阅源