Lesson 19
Binary Trees & Traversals
Pre-order, in-order, post-order, level-order — four ways to visit every node.
01Why it matters & the intuition
File systems, the DOM, compilers' syntax trees and decision trees are all trees. Nearly every tree problem is one of four traversals plus a little bookkeeping.
Think of it like…
A family tree printed on paper. You can read it top-down generation by generation (level-order), or trace one branch all the way down before backing up (depth-first). Depth-first comes in three flavours depending on *when* you write down the parent: before its children, between them, or after them.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- visiting
- recorded
03Key ideas
Anatomy
Each node has a value, a left and a right child (either may be null). The top node is the root; nodes without children are leaves.
Depth-first orders
Pre-order: node, left, right. In-order: left, node, right. Post-order: left, right, node. Recursion makes all three three lines long.
Level-order (BFS)
Use a queue: dequeue a node, record it, enqueue its children. Visits the tree ring by ring.
Height
Height = 1 + max(height(left), height(right)). A balanced tree of n nodes has height ≈ log n; a degenerate one has height n.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class TreeNode {
constructor(
public value: number,
public left: TreeNode | null = null,
public right: TreeNode | null = null,
) {}
}
function preorder(n: TreeNode | null, out: number[] = []): number[] {
if (!n) return out;
out.push(n.value);
preorder(n.left, out);
preorder(n.right, out);
return out;
}
function inorder(n: TreeNode | null, out: number[] = []): number[] {
if (!n) return out;
inorder(n.left, out);
out.push(n.value);
inorder(n.right, out);
return out;
}
function levelOrder(root: TreeNode | null): number[][] {
const levels: number[][] = [];
let frontier = root ? [root] : [];
while (frontier.length) {
levels.push(frontier.map((n) => n.value));
frontier = frontier.flatMap((n) => [n.left, n.right].filter((c): c is TreeNode => c !== null));
}
return levels;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Any full traversal | O(n) | — |
| Recursive DFS space | — | O(h), h = height |
| Level-order space | — | O(w), w = max width |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Maximum depth
Write max_depth(root) returning the number of nodes on the longest root-to-leaf path. Nodes look like { value, left, right }; an empty tree is None (depth 0). Tests are given in level-order with None gaps.
Nodes have .value, .left and .right.