Breadth-first & balance

Breadth-first traversal takes the tree a level at a time: the root, then both its children, then all four grandchildren. Where depth-first leans on the call stack, breadth-first leans on a FIFO queue — take a node from the front, record it, add its children to the back. The same level structure is what makes a balanced tree fast: n nodes fit in about log₂ n levels, so a search descends only that far.

Step through the levels and watch the queue fill and drain. Then see what happens to the cost when the tree is balanced — and when it is not.

Level by level, with a queue Advanced: balance & O(log n)

Level by level, with a queue

The queue holds nodes waiting to be visited. Start with the root; each time you take one from the front, record its value and push its children to the back. Step through the three levels and read the visited sequence and the queue after each level.

The level · select one

visited: 12

queue: [8, 30]

A queue turns recursion inside out: instead of going deep and returning, you keep a running line of what to visit next, oldest first. That same line, level by level, is what a balanced tree keeps short.

Advanced: balance & O(log n)

The number of levels is the cost of a search. A balanced tree of n nodes has about log₂ n levels — seven nodes in three, a thousand in ten — so a lookup descends ten steps, not a thousand. But balance is not automatic: insert 1, 2, 3, 4 in order and every node hangs to the right, producing a chain as tall as the list is long. The tree has decayed back into a list, and search is O(n) again.

Self-balancing trees (AVL, red-black) rotate subtrees after each insert to hold the height near log n. The trie family takes the idea further: a wide branching factor makes the tree so shallow it behaves as constant-depth — the subject of F4.05 onward.

Same keys, two shapes · balanced vs degenerate

Insert 1, 2, 3, 4 in sorted order and the right-hand shape is what you get — a linked list wearing a tree’s clothes. Keeping the left shape is the entire job of a self-balancing tree.

def level_order(root), do: walk([root], [])
defp walk([], acc), do: Enum.reverse(acc)
defp walk([nil | rest], acc), do: walk(rest, acc)
defp walk([{v, l, r} | rest], acc), do: walk(rest ++ [l, r], [v | acc])
# 12, 8, 30, 5, 10, 20, 42  (use :queue for O(1) enqueue in real code)

The idea

Cost is the number of levels; balance keeps that number near log n, and losing balance costs you O(n).

In Elixir

A FIFO queue walks levels; a balanced tree keeps the descent at log₂ n.

That completes F4.02. Next module: F4.03 — Sorting & searching (in production), where binary search applies this same halving to a sorted sequence, and merge sort builds order bottom-up.

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.