F4 · Foundations · module 2
Trees & traversals
Give a list two tails instead of one and it becomes a tree. The cons cell’s single pointer splits into a left and a right, and the linear walk of F4.01 becomes a traversal — depth-first or breadth-first. When the tree stays balanced, the O(n) walk of a list collapses to an O(log n) descent, which is the whole reason trees exist and the road into the trie family later in this chapter.
The running example is a seven-node binary search tree. Three angles open the module: its recursive shape, the three depth-first orders, and the breadth-first level order — then an advanced look at balance and the descent to tries.
In-order traversal
in-order: ·
Visit the left subtree, the node, then the right — on a BST this comes out sorted.
A tree is a branching list
A binary tree is a node — a value with a left and a right subtree — or the empty tree
nil. That is the cons cell with a second pointer. Select an angle to see the same
tree as a shape, a depth-first walk, or a breadth-first sweep.
The angle · select one
role: {value, left, right}
order: 7 nodes · height 3 · a root over two subtrees
The shape is recursive, so the functions are too: every tree operation handles a node by combining
results from its two subtrees, bottoming out at nil. The order in which you combine
them is what makes a traversal pre-, in-, post-, or level-order.
Three deep dives
In order: the recursive shape and the functions that fold it; the three depth-first orders and what each is for; then breadth-first level order, balance, and the O(log n) descent.
{value, left, right} or nil. Size, height, and sum by recursion — plus structural sharing on insert.Advanced: balance & the road to tries
A binary search tree keeps its left subtree below the node and its right subtree above it, so a lookup
compares once per level and descends one side — O(height) work. For a balanced tree of
n nodes the height is about log₂ n, so search, insert,
and delete are O(log n). The catch is the word balanced: insert 1, 2, 3, 4 in
order and the tree degenerates into a right-leaning chain — a list with extra steps, back to O(n).
Self-balancing trees (AVL, red-black) restore logarithmic height after each insert by rotating subtrees.
The trie family later in this chapter takes a different route to the same goal: instead of two children per
node, a HAMT (F4.05) gives each node up to thirty-two, indexed by a slice of the key’s
hash. A branching factor that high makes the tree shallow — height about log₃₂ n,
effectively constant for any realistic map — which is how Elixir’s own Map
gets fast persistent lookup.
# a balanced BST of n nodes: height ~ log2(n), search O(log n) # inserted in sorted order, the same keys degenerate: 1 -> 2 -> 3 -> 4 # a right-leaning chain — height n, search O(n) # a HAMT node branches 32 ways on hash bits: # height ~ log32(n) — shallow enough to act constant-time
F4.01 · a list walk is O(n)
One pointer per cell means reaching the end touches every cell.
F4.02 · a balanced descent is O(log n)
Two pointers per node halve the search each step — if the tree stays balanced.
Start with the recursive shape, then depth-first orders, then breadth-first & balance. Next module: F4.03 — Sorting & searching, where binary search reuses exactly this halving idea over a sorted sequence.
References
Primary sources for this lesson, and where it connects in the course.
Sources
- Tree traversal — Wikipedia — depth-first and breadth-first orders.
- Okasaki, C. (1996). Purely Functional Data Structures (thesis) — trees, functionally.