Lessons · #5 of 11

Binary Trees

One node, two children — every recursive data structure

Binary tree · traversal orders

pick a traversal → · preorder / inorder / postorder / level

init

value

Try it: Insert a few values. Then try each traversal — preorder, inorder, postorder, level — and watch the visit order light up under the tree.

Why it matters

Trees are the natural structure for hierarchical data: file systems, HTML documents, organization charts, decision trees. Binary trees are the foundation for BSTs, heaps, and expression parsing.

The idea

Imagine a family tree, but each person has at most two children (left and right). Start from a single root ancestor.

That's a binary tree. Each node has at most two children.

Trees unlock new ways to organize data:

Hierarchy: Natural for parent-child relationships
Recursion: Every subtree is itself a tree - problems decompose beautifully
Multiple paths: Unlike linear structures, trees branch

Traversals visit nodes in different orders:

Pre-order: Process node, then children (serialization)
In-order: Left child, node, right child (sorted order in BST)
Post-order: Children first, then node (deletion)
Level-order: Layer by layer using a queue (BFS)

Key takeaways

Each node has at most 2 children (left and right)
Height determines efficiency - balanced is O(log n), unbalanced can be O(n)
Four traversal orders: pre-order, in-order, post-order, level-order
Foundation for BSTs, heaps, expression trees

Going deeper

A complete binary tree fills each level before starting the next (except possibly the last level). A full binary tree has every node with 0 or 2 children. A perfect binary tree is both complete and full. These distinctions matter for heap implementations (which require complete) and tree balancing.

The "max nodes at level k = 2ᵏ" formula falls out by induction: level 0 has one node (the root); each level has at most twice the previous. Summing the geometric series from level 0 to height h yields 2^(h+1) − 1 nodes max. Inverting: a balanced tree of n nodes has height ⌊log₂ n⌋.

In the wild

File systems. Directories form a tree (with some symlinks turning it into a DAG). find / is just a tree traversal.
DOM trees. Every HTML document is a tree; CSS selectors and DOM queries are traversal patterns. getElementById is a hash-table layered on top to make lookup O(1).
Scene graphs in graphics + robotics. A robot's URDF (Unified Robot Description Format) is a tree of links connected by joints; computing a hand's pose in world frame is a chain of matrix multiplications walking from leaf to root.
Octrees and KD-trees. Spatial subdivision trees power collision detection, point-cloud nearest-neighbor (used by every SLAM system), and ray tracing.
Expression trees. Every compiler turns source code into an AST — a tree where operators are interior nodes and operands are leaves. The traversal order chooses your evaluation strategy.

Math details

Tree properties: max nodes at level k 2ᵏ; max nodes in tree, height h 2ʰ⁺¹ − 1; min height, n nodes ⌊log₂ n⌋; max height (degenerate) n − 1
Traversal time: O(n) — every node visited exactly once
Space: recursive traversal O(h) on the call stack; iterative (BFS) O(w) where w is the widest level

Implementation

Binary Tree Node

struct TreeNode<T> {
    data: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

// In-order traversal (recursive)
fn inorder(node: Option<&Box<TreeNode<T>>>) {
    if let Some(n) = node {
        inorder(n.left.as_ref());
        process(n.data);
        inorder(n.right.as_ref());
    }
}

Traversal Orders

Pre-order: Node -> Left -> Right
In-order: Left -> Node -> Right
Post-order: Left -> Right -> Node
Level-order: BFS with queue

Practice

Three problems, each teaching a different recursion shape:

Maximum Depth — easy · plain two-line recursion (1 + max(left, right)); the warm-up every tree interview opens with
Level-Order Traversal — medium · tree meets queue; BFS with a "snapshot the size" trick to recover levels
Diameter of Binary Tree — medium · the "two-values-per-recursion" pattern — return height, side-effect the best

→ Browse all practice problems

🌳 Binary Trees