Trees & Traversals

A tree is the most natural data structure humans have ever named. Draw your family tree. Sketch the org chart for a company. Expand the folders on your hard drive. Every one of them is a tree — nodes connected by parent-child edges, with a single root at the top and no cycles anywhere.

Once you have a tree, the inevitable question is: in what order do you visit every node? That question has exactly four important answers, and each one turns out to be useful for something different.

The vocabulary

Before algorithms, a few terms you will see constantly:

A binary tree constrains each node to at most two children, conventionally called left and right. Most classic tree algorithms assume binary trees, though the ideas generalise.

        1          ← root, depth 0, height 2
       / \
      2   3        ← depth 1
     / \ / \
    4  5 6  7      ← depth 2, all leaves, height 0

Height of the whole tree = height of the root = 2. Each leaf’s height = 0.

The core question: which node next?

There are exactly two high-level strategies for visiting every node:

• Breadth-first (BFS) — finish every node on the current level before going deeper. Uses a queue.
• Depth-first (DFS) — commit to one path all the way down before backtracking. Uses a stack (either the call stack via recursion, or an explicit one).

DFS has three variants depending on when you process the root relative to its subtrees: pre-order, in-order, and post-order.

Try it: all four traversals on one tree

Step through each mode. Notice how the queue/stack panel changes — that internal structure is the entire difference between the four algorithms.

Level-order (BFS)

Process every node at depth 0, then every node at depth 1, then depth 2, and so on. The mechanism is a queue: enqueue the root, then loop — dequeue a node, visit it, enqueue its children.

Queue after each step (7-node tree):
Start: [1]
Visit 1, enqueue 2, 3   → [2, 3]
Visit 2, enqueue 4, 5   → [3, 4, 5]
Visit 3, enqueue 6, 7   → [4, 5, 6, 7]
Visit 4 (no children)   → [5, 6, 7]
Visit 5                 → [6, 7]
Visit 6                 → [7]
Visit 7                 → []

Result: 1 → 2 → 3 → 4 → 5 → 6 → 7

The FIFO property of the queue is what enforces level order. Every node’s children are added to the back while we’re still working through nodes added earlier, so the current level drains completely before the next one begins.

When to use BFS: finding the shortest path in an unweighted graph, finding the nearest node that satisfies a condition, building tree level-by-level output (e.g., a JSON tree view).

DFS: pre-order, in-order, post-order

All three DFS variants share the same recursive skeleton. The only difference is where the visit call sits:

def pre_order(node):
    visit(node)         # root FIRST
    pre_order(node.left)
    pre_order(node.right)

def in_order(node):
    in_order(node.left)
    visit(node)         # root BETWEEN
    in_order(node.right)

def post_order(node):
    post_order(node.left)
    post_order(node.right)
    visit(node)         # root LAST

One line changes. Three completely different visit sequences.

Pre-order: root, left, right

Visit the root before either subtree. Result on the 7-node tree: 1 2 4 5 3 6 7.

Useful for: copying a tree (you need to create the root before its children), serialising a tree to a file, generating prefix expressions from an expression tree (e.g., + * 2 3 4 for (2 * 3) + 4).

In-order: left, root, right

Visit the entire left subtree, then the root, then the right subtree. Result: 4 2 5 1 6 3 7.

For a binary search tree (BST), in-order is special: because the BST invariant places smaller values on the left, in-order traversal visits nodes in sorted ascending order. That’s why in-order is the canonical way to read a BST.

Post-order: left, right, root

Visit both subtrees fully before the root. Result: 4 5 2 6 7 3 1.

Useful for: deleting a tree (you must free children before the parent), evaluating an expression tree bottom-up, computing the size or height of a tree (children’s answers needed before the parent’s).

Iterative DFS with an explicit stack

The recursive versions are clean, but every language has a call-stack depth limit (Python’s default is ~1000). For deep or large trees, an iterative approach is safer:

def iterative_pre_order(root):
    if root is None:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()        # LIFO — stack top is the next to visit
        result.append(node.val)
        if node.right:
            stack.append(node.right)   # push right first
        if node.left:
            stack.append(node.left)    # so left is popped first
    return result

Pushing right before left ensures left is always on top of the stack and therefore visited first — mimicking the recursive call order.

Build and run it

The code below defines a tiny Node class, builds the 7-node tree, and prints all three DFS walks.

Quick check