🧩 Data Structures & Algorithms · Chapter 13

Tree traversals

Same tree, four walks, four different lists. Which one you pick decides whether you get sorted keys, a copy, a safe delete or a level-by-level view.

Study this lesson free in the app →

The basics

A tree traversal visits every node of a tree exactly once, in a fixed order. There are four standard orders.

The problem it solves: a list has one obvious order — front to back. A tree branches, so at every node you must decide: handle this node now, or after its children? Go deep first, or across first? Each choice produces a different sequence, and each sequence solves a different problem.

The mental model: exploring a building. Preorder is a visitor who writes a room's name on entering, then explores its sub-rooms. Postorder is the movers who can only clear a room after every room inside it is empty. Inorder reads left, middle, right — on a BST that is smallest to largest. Level order is a fire warden sweeping floor by floor.

Cost: every traversal is O(n) time. Depth-first walks use O(h) extra space (h = height) for the stack; level order uses O(w) (w = widest level) for its queue.

Explained

One tree:

          8
        /   \
       4     12
      / \      \
     2   6      14

• Inorder → 2 4 6 8 12 14 (sorted!)
• Preorder → 8 4 2 6 12 14
• Postorder → 2 6 4 14 12 8
• Level order → 8 4 12 2 6 14

The next four reels animate each one on this exact tree. Predict before you press play.

One rule, four orders, one cost

Depth-first traversal is one recursive function. Only the position of visit(node) changes:

pre(node):  visit(node); pre(left);  pre(right)
in(node):   in(left);  visit(node);  in(right)
post(node): post(left); post(right); visit(node)

Level order is different: put the root in a queue; repeatedly take the front node, visit it, add its children to the back. First in, first out means a whole level finishes before the next begins.

Cost:

• Time: O(n) for all four — each node is visited once, each edge followed once.
• Space: DFS holds one root-to-node path on the stack → O(h): O(log n) if balanced, O(n) if degenerate. Level order holds up to one full level in the queue → O(w), which is about n/2 for the bottom of a full tree.

Inorder: left, node, right

Go all the way left to 2, print it, back up to 4, then into 6, then 8, then the right side. Because this tree is a BST, the output is 2 4 6 8 12 14 — sorted. That's the single most-used fact about inorder.

Preorder: node first

Print the node the moment you arrive, then do its left subtree, then its right: 8 4 2 6 12 14. The root always comes first, so replaying the sequence as inserts rebuilds the same tree — that's why preorder is used to copy and serialise trees.

Postorder: children first

A node is printed only after both its subtrees are done: 2 6 4 14 12 8. The root comes last. Use it whenever a node's answer depends on its children — deleting a tree, computing heights or folder sizes, evaluating an expression.

Level order: floor by floor

A queue starts with 8. Take 8, add 4 and 12. Take 4, add 2 and 6. Take 12, add 14. Then 2, 6, 14. Output 8 4 12 2 6 14 — each level left to right. This is BFS on a tree.

All four in Python

from collections import deque

def preorder(n, out):
    if n:
        out.append(n.val)
        preorder(n.left, out)
        preorder(n.right, out)
    return out

def inorder(n, out):
    if n:
        inorder(n.left, out)
        out.append(n.val)
        inorder(n.right, out)
    return out

def postorder(n, out):
    if n:
        postorder(n.left, out)
        postorder(n.right, out)
        out.append(n.val)
    return out

def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        n = q.popleft()                  # O(1); list.pop(0) is O(n)
        out.append(n.val)
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)
    return out

def height(n):                           # postorder thinking
    return -1 if n is None else 1 + max(height(n.left), height(n.right))

Gotchas

• Mixing up pre and post — say the rule out loud: the prefix tells you when the node is visited (pre = before children).
• Using a list as a queue — list.pop(0) shifts every element: O(n) per pop, O(n²) total. Use collections.deque.
• Deep recursion — a 5,000-node chain-shaped tree crashes a recursive walk in Python. Use an explicit stack.
• Claiming O(1) or O(log n) space — DFS is O(h), which is O(n) for a degenerate tree; BFS is O(w).
• Thinking inorder means sorted for any tree — only for a BST.
• Rebuilding from one traversal — inorder alone (or preorder alone, without null markers) is ambiguous.

Words to know

In two minutes

• Every traversal visits all n nodes once: O(n) time.
• The three depth-first orders differ only in when the node is handled: before its children (pre), between them (in), after them (post).
• Inorder on a BST gives sorted keys; preorder copies or serialises a tree; postorder deletes or computes from children up (sizes, heights, expression values).
• Level order uses a queue and visits the tree level by level — the basis of BFS and 'shortest number of steps' answers.
• Space: DFS uses O(h) stack — O(log n) balanced, O(n) degenerate. Level order uses O(w) queue — up to ~n/2 on the bottom level of a full tree.
• Recursion is the natural way to write DFS; an explicit stack avoids Python's ~1,000-frame limit on deep trees.
• Inorder alone cannot rebuild a tree; inorder plus preorder (or postorder) with unique keys can.

Test yourself

There are 8 questions, 4 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.