Trees & Binary Trees: Traversals

A linked list is a line, each node pointing to one next node. Cut that restriction, let a node point to several others, and the line branches into a tree. Trees are how computers model anything hierarchical: a file system of folders inside folders, the HTML on this page, a company org chart, a family tree. The shape is everywhere once you see it.

The vocabulary, fast

A tree is a set of nodes connected by edges, with one node at the top called the root. From there it grows downward (computer-science trees are drawn upside down, root on top, leaves at the bottom).

• Root: the single node at the top, with no parent.
• Child: a node directly below another. Parent: the node directly above.
• Leaf: a node with no children, the end of a branch.
• Subtree: any node together with everything hanging below it.

A binary tree adds one rule: every node has at most two children, conventionally called left and right. That cap of two is what makes binary trees so common. They're simple to reason about and they power things like the search trees coming up next.

That's a binary search tree (BST): for every node, everything in its left subtree is smaller and everything in its right subtree is larger. 5 is the root, 3 and 8 are its children, and 1, 4, 7, 9 are leaves. We build trees like this throughout the rest of the post.

Visiting every node: traversals

Knowing the shape is one thing. The real question is: in what order do you visit the nodes? A list has one obvious order, front to back. A tree branches, so there are several, and each is useful for different jobs. There are four classic traversals.

The first three are depth-first: they dive down a branch before backing up. They differ only in when they record the current node relative to its children:

• In-order: left subtree, then current node, then right subtree.
• Pre-order: current node first, then left, then right.
• Post-order: left, then right, then current node last.

The fourth is level-order (also called BFS, breadth-first search): visit the tree row by row, top to bottom, left to right, instead of diving down.

In-order has a lovely property on a BST: it spits the values out sorted. Watch it visit the same tree from above — left, node, right, all the way down:

That came out 1, 3, 4, 5, 7, 8, 9, perfectly sorted. That's not luck. It's the BST ordering rule meeting the in-order rule. "Always take the smaller (left) side first" walks the values in ascending order.

Now the same tree, but level-order (BFS). Instead of plunging down a branch, it sweeps each row before moving to the next:

BFS visited 5 (the root), then 3, 8 (the next row), then 1, 4, 7, 9 (the bottom row). Depth-first goes deep first, breadth-first goes wide first. BFS is the traversal that uses a queue, exactly the FIFO structure from the stacks and queues lesson, to remember which nodes to visit next.

The three depth-first traversals in Python

Depth-first traversals are naturally recursive: to traverse a tree, traverse its left subtree, deal with the node, traverse its right subtree, and "traverse a subtree" is the same function calling itself. The only thing that changes between in/pre/post-order is where you record the current node. Run this on the same tree:

Look at the three outputs. In-order is sorted (1, 3, 4, 5, 7, 8, 9). Pre-order starts with the root 5 because it records the node before recursing. Post-order ends with the root 5 because it records the node after both children. Same tree, same recursion skeleton, and only the position of one append line changes the entire order.

Where this is heading

A tree is a hierarchy: a root at the top, parents pointing to children, leaves at the bottom. A binary tree caps each node at two children. You read a tree by traversing it: in-order (sorted, on a BST), pre-order (root first), post-order (root last), or level-order (row by row, powered by a queue). The depth-first three are the same recursion with one line moved.

You've now seen the binary search tree shape twice. Next: Binary Search Trees, where that left-smaller / right-larger rule turns a tree into a structure you can search, insert into, and delete from in O(log n).