Trees — BFS, DFS, and why ML loves them

Trees are everywhere in computer science. File systems. HTML's DOM. Decision trees and random forests in ML. Heaps. Tries. Parser ASTs. JSON's nested objects. Categorisation hierarchies.

The formal definition — a connected acyclic graph. Connected means every node is reachable from every other. Acyclic means no loops. From these two properties, you get exactly n-1 edges in any tree of n nodes. (Any more and you'd have a cycle; any fewer and you'd be disconnected.)

The vocabulary you'll use:

Root — the node we start from. Trees are typically rooted, even though graphs in general aren't.

Node — any entry in the tree. Has an optional value, optional children (other nodes), and optionally a parent pointer.

Leaf — a node with no children.

Internal node — a node with at least one child. Includes the root if the tree has more than one node.

Depth — distance from root to a node, measured in edges.

Height — depth of the deepest leaf in the subtree.

Balanced tree — height stays around O(log n). Insertions and deletions stay fast.

Unbalanced tree — height can be O(n). Degenerates to a linked list. Operations slow to O(n).

In ML, trees show up most prominently in decision trees and ensembles (random forests, gradient boosting). Each internal node is a split decision (feature X < threshold). Each leaf is a prediction. The tree's depth controls overfitting — too deep memorises training data; too shallow underfits.

Most tree problems boil down to 'walk the tree in some order, do something at each node'. The walking algorithm is BFS or DFS (covered next). The 'something' is the problem-specific logic.

Learn the traversals. Most tree problems become tractable.

Two ways to depth-first search a tree. Both visit every node; both run in O(n) time and O(h) space (where h is height). They differ in HOW they manage the bookkeeping.

Recursive DFS:

def dfs(n):
    if n is None: return
    visit(n)
    dfs(n.left)
    dfs(n.right)

Three lines. Reads as English. The call stack handles the bookkeeping — each call gets its own frame, returning unwinds the stack, the recursion mirrors the tree's structure.

Iterative DFS:

stack = [root]
while stack:
    n = stack.pop()
    if n is None: continue
    visit(n)
    stack.append(n.right)   # right first, so left pops first
    stack.append(n.left)

More lines. We maintain an explicit stack of nodes to visit. Pop one off, visit it, push its children (right before left, so left pops first — pre-order).

Which to use?

Recursive is cleaner for balanced trees and interview problems. The code is shorter and matches the tree's recursive structure.

Iterative is required for production code on potentially deep trees. Python's default recursion limit is 1000. A skewed tree (effectively a linked list) of depth 5000 will RecursionError. Iterative has no such limit; the explicit stack lives on the heap, which is much bigger than Python's stack.

For file-system traversals, large LLM token streams, or any user-supplied data of unbounded depth — iterative.

For balanced binary trees up to depth ~1000 — recursive.

A hybrid — recursive with @sys.setrecursionlimit increased to a reasonable number (say 10000). Combines clean code with reasonable headroom. Acceptable for trees you have control over.

Both approaches visit nodes in the same order (for pre-order specifically). Same algorithm, different implementations of the bookkeeping.

Breadth-first search on a tree gives you level-order traversal. Useful for problems like 'right-side view', 'level-by-level averages', 'zigzag traversal', 'serialize a tree'.

The shape uses a deque (yesterday's lesson — list.pop(0) is O(n); deque.popleft is O(1)). For each level, we know how many nodes are in the queue (it's len(q) before we start the inner loop). Process exactly those, push their children, move to the next level.

Look at the snippet. The outer while-loop iterates levels. The 'for _ in range(len(q))' inner loop processes exactly this level — even though we're appending children to the queue inside the loop, we only iterate the original count, so children are processed in the next outer iteration.

The key trick — taking len(q) at the start of each outer iteration. Without this, the inner loop would consume children at this level along with the parents, and you'd lose the level boundary.

Return structure — a list of lists, one inner list per level. Adapts easily to other questions:

Right-side view — within each level, take the LAST node's value.

Level averages — within each level, sum and divide by count.

Zigzag — within each level, reverse the order on even-indexed levels.

Maximum value per level — within each level, take max.

The code structure stays the same. Specialise the per-level reduction.

Time complexity — O(n) total, every node visited once. Space complexity — O(w) where w is the maximum width of the tree, which is bounded by n in the worst case (a complete tree's last level has n/2 nodes).

Level-order is BFS adapted to trees. The same template appears in graph problems (Day 26).

If your application does many 'starts-with' queries on a fixed dictionary of strings — autocomplete, spellcheck, IP routing — a trie outperforms anything else.

A trie (pronounced 'try', from re-trie-val) is a tree where each edge is a character, and each path from root to a node spells a prefix. Strings end at marked 'end-of-word' nodes.

Searching for 'a string starts with prefix P' is O(len(P)). Walk down the trie following P's characters; if you can, the prefix exists; if at any point the edge isn't there, the prefix doesn't exist. CRUCIALLY — independent of dictionary size. A trie with one million strings answers the same prefix query in the same time as one with one thousand.

Use cases beyond autocomplete:

Spellcheck. Maintain a trie of valid words. Walk the input character by character; suggest corrections when paths fail.

IP routing tables. Each prefix is an IP block. Routers use compressed tries (Patricia tries) for O(1) prefix matching at line speed.

Fastest token-prefix matching for tokenisers. Some BPE implementations use tries for matching the longest prefix.

Unique prefix detection. Find the shortest prefix that uniquely identifies each string in a set. Useful for compressed code generation.

In Python, tries are easy to roll. Use a dict of dicts where each level represents a character. End-of-word marked with a sentinel ('_end' or similar).

For production, use marisa-trie (compact, immutable, very fast). For prototyping, hand-rolled is fine.

Most developers go their whole career without writing a trie because their problems don't need them. When you DO need 'starts-with' queries on a dictionary, no other structure comes close.

End of Day 25. Trees are the structure that bridges DSA into both ML (decision trees, random forests) and systems work (file systems, parsers, ASTs).

What we covered.

Morning, the formal foundation. A tree is a connected acyclic graph. n nodes, exactly n-1 edges. Vocab — root, leaf, depth, height, balance. ML applications include decision trees and ensembles, where balance and depth control overfitting.

Midday, DFS recursive vs iterative. Same algorithm, different bookkeeping. Recursive is clean for interview-sized problems; iterative is required for production code on unbounded-depth data.

Afternoon, the level-order BFS template in 12 lines. Process exactly len(q) nodes per outer iteration; that gives you the level boundary. Same template adapts to right-side view, level averages, zigzag, max-per-level.

Evening, tries as the structure for prefix queries. O(L) per query, independent of dictionary size. Use cases — autocomplete, spellcheck, IP routing, tokeniser prefixes. Most engineers go years without writing one; when you need it, nothing else compares.

A broader thought. Trees are the right structure for hierarchical data, and most hierarchical data is more common than people realise. Decision trees, parse trees, file systems, JSON — all trees. Mastering tree traversals is the foundation that makes graphs (tomorrow) tractable.

Tomorrow, Day 26, graphs. Adjacency lists, BFS for shortest path, Dijkstra for weighted shortest path, topological sort for dependency resolution. The most-used data model in computer science.

See you in the morning.