Trees & Traversals

A tree is the most natural structure people have ever named.

Draw your family tree. Sketch the org chart at a company. Open the folders on your computer, each holding more folders. Every one of these is a tree: nodes joined by parent-child links, with a single node at the top and no loops anywhere. And the moment you have a tree, one question becomes unavoidable — in what order do you visit all the nodes? That question has exactly four useful answers, and each turns out to be right for a different job.

A little vocabulary first

A few words you will meet constantly. The root is the single top node, with no parent. A leaf is a node with no children. A node’s depth is how many steps it is below the root, and a tree’s height is the longest path from the root down to a leaf. A binary tree simply restricts each node to at most two children, called left and right — the shape most classic algorithms assume.

Here is the small tree we will walk all four ways:

Two ways to choose the next node

There are really only two strategies for visiting every node, and they differ in one instinct: do you go wide or deep first?

Breadth-first (BFS) finishes a whole level before going one step deeper, and it runs on a queue. You enqueue the root, then repeat: take the front node, visit it, and enqueue its children at the back. Because the queue is first-in-first-out, every node’s children wait behind the nodes already queued, so the current level drains completely before the next begins:

queue: [1]                 visit 1, add 2, 3
queue: [2, 3]              visit 2, add 4, 5
queue: [3, 4, 5]          visit 3, add 6, 7
queue: [4, 5, 6, 7]       visit 4, 5, 6, 7

level order: 1 2 3 4 5 6 7

Depth-first (DFS) commits to one path all the way down before backtracking, and it runs on a stack — usually the call stack, through recursion. DFS comes in three flavours that differ only in when you visit the root relative to its two subtrees:

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

def in_order(node):      # root in the MIDDLE
    in_order(node.left); visit(node); in_order(node.right)

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

One line moves, and the visiting order changes completely. On our tree:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))

def walk(node, order, out):
    if node is None:
        return
    if order == "pre":  out.append(node.val)
    walk(node.left, order, out)
    if order == "in":   out.append(node.val)
    walk(node.right, order, out)
    if order == "post": out.append(node.val)

for order in ("pre", "in", "post"):
    out = []; walk(root, order, out)
    print(f"{order:5}-order:", out)

pre  -order: [1, 2, 4, 5, 3, 6, 7]
in   -order: [4, 2, 5, 1, 6, 3, 7]
post -order: [4, 5, 2, 6, 7, 3, 1]

What each order is good for

• Pre-order (root first) copies or serialises a tree — you must create a node before its children. It also produces prefix expressions from an expression tree.
• In-order (root in the middle) has a special gift on a binary search tree: because smaller values sit on the left, in-order visits everything in sorted ascending order. That is the canonical way to read a BST.
• Post-order (root last) is for anything that needs the children’s answers first — freeing a tree (free children before the parent), evaluating an expression bottom-up, or summing folder sizes from the leaves up.
• Level-order (BFS) finds the shallowest node meeting a condition, or the shortest path in an unweighted graph — anything where “closest first” matters.

Practice