S028 · Trees & BSTs — Traversal (BFS/DFS)

Module M03: Data Structures & Algorithms · Session 28 of 130 · Track: SW 🌳

What you'll be able to do after this session

• Explain Trees & BSTs to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S027 — Recursion — Call Stack, Base Case, Worked Examples

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Trees explained (NeetCode) — the basics in 10 minutes.
• 🎥 Deep dive (30–60 min) · Binary Search Trees — full walkthrough (MIT / Erik Demaine) — invariants, operations, complexity.
• 🎥 Hands-on demo (10–20 min) · BFS vs DFS on trees (NeetCode) — traversal patterns side by side.
• 📖 Canonical article · Wikipedia — Binary search tree — invariants and standard operations.
• 📖 Book chapter / tutorial · Wikipedia — Tree traversal — inorder / preorder / postorder / BFS in one page.
• 📖 Engineering blog · PostgreSQL docs — B-Tree indexes — where trees actually live in production databases.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Hierarchical data everywhere.

A tree is what happens when a linked list has ambition. Instead of each node pointing to one "next" node, it points to multiple children. The topmost node is the root; nodes with no children are leaves. There are no cycles — start from the root, and you can reach every node exactly one way.

Trees are the natural shape of hierarchy in the real world: file systems, DOM, organisation charts, XML/JSON, dependency trees, decision trees, category taxonomies. Any time the answer to "does A contain B?" is meaningful, you probably want a tree.

A binary tree is a tree where every node has at most two children (left and right). A binary search tree (BST) adds an ordering rule: for every node, everything in the left subtree is smaller, everything in the right subtree is larger. That single invariant turns search from "look through all n nodes" (O(n)) into "compare and go left or right" (O(log n) if balanced) — exactly like binary search on a sorted array, but with cheap insertion.

Traversal is how you visit every node. DFS (depth-first: preorder / inorder / postorder) is naturally recursive. BFS (breadth-first, level by level) uses a queue.

One-sentence gotcha to carry forever: A plain BST degenerates into a linked list if you insert sorted data — inserting 1, 2, 3, 4, 5 in order gives a right-only chain of depth 5, and all operations degrade from O(log n) to O(n). Production systems use self-balancing variants (AVL, red-black, B-tree) to guarantee O(log n) no matter the insert order.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

A tree with vocabulary:

That's a valid BST: 3 < 8, 10 > 8, 1 < 3, 6 > 3, and so on recursively.

Worked example — search for 6 in the BST above:

1. At root 8: 6 \< 8, go left.
2. At 3: 6 > 3, go right.
3. At 6: found! Return in 3 comparisons.

Compare to a linear scan of 7 nodes. On a million-node balanced BST, search takes ~20 comparisons instead of a million.

The four traversal orders (on the same tree):

Notice: inorder on a BST gives you the values in sorted order. That's a defining property; if inorder isn't sorted, it isn't a valid BST.

Complexity table:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# trees_bst_playground.py
from collections import deque
 
class BSTNode:
    __slots__ = ("v", "left", "right")
    def __init__(self, v):
        self.v, self.left, self.right = v, None, None
 
def bst_insert(root, v):
    if root is None:
        return BSTNode(v)
    if v < root.v: root.left = bst_insert(root.left, v)
    elif v > root.v: root.right = bst_insert(root.right, v)
    return root  # duplicates ignored
 
def bst_search(root, v):
    while root:
        if v == root.v: return True
        root = root.left if v < root.v else root.right
    return False
 
# ---- 1. Build a BST and search it ----
root = None
for x in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = bst_insert(root, x)
 
print("search 6:", bst_search(root, 6))
print("search 9:", bst_search(root, 9))
 
# ---- 2. Four traversals ----
def preorder(n):  return [] if not n else [n.v] + preorder(n.left) + preorder(n.right)
def inorder(n):   return [] if not n else inorder(n.left) + [n.v] + inorder(n.right)
def postorder(n): return [] if not n else postorder(n.left) + postorder(n.right) + [n.v]
def bfs(n):
    if not n: return []
    out, q = [], deque([n])
    while q:
        node = q.popleft()
        out.append(node.v)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out
 
print("
preorder :", preorder(root))
print("inorder  :", inorder(root))
print("postorder:", postorder(root))
print("bfs      :", bfs(root))
 
# ---- 3. Verify BST invariant ----
def is_bst(n, lo=float("-inf"), hi=float("inf")):
    if not n: return True
    if not (lo < n.v < hi): return False
    return is_bst(n.left, lo, n.v) and is_bst(n.right, n.v, hi)
 
print("
is_bst:", is_bst(root))
# now corrupt it and re-check
root.right.v = 2   # violates: right of 8 shouldn't be 2
print("after corruption:", is_bst(root))
 
# ---- 4. Watch a skewed BST degenerate to a linked list ----
def height(n): return 0 if not n else 1 + max(height(n.left), height(n.right))
 
good = None
for x in [50,25,75,10,30,60,90]:  # roughly balanced
    good = bst_insert(good, x)
 
bad = None
for x in range(1, 8):              # sorted insert -> right-only chain
    bad = bst_insert(bad, x)
 
print(f"
balanced-ish tree height: {height(good)}  (7 nodes)")
print(f"sorted-insert tree height: {height(bad)}   (7 nodes)   <-- degenerated!")

Checklist:

1. search 6 returns True, search 9 returns False.
2. Inorder prints [1, 3, 4, 6, 7, 8, 10, 13, 14] — sorted.
3. Preorder, postorder, and BFS produce the expected sequences.
4. is_bst returns True initially, False after corruption.
5. Balanced height is 3–4; sorted-insert height is 7 (a linked list in disguise).

Try this modification: implement bst_delete(root, v) handling the three cases (leaf, one child, two children — swap with inorder successor). This is the fiddliest BST operation; getting it right is a rite of passage.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Plain unbalanced BSTs almost never exist in production code — the "sorted insert makes it a linked list" failure is too easy to trigger accidentally. What actually ships:

1. Self-balancing BSTs. Java's TreeMap / TreeSet use red-black trees. C++'s std::map / std::set typically use red-black. Rust's BTreeMap uses a B-tree variant. These all guarantee O(log n) for every operation regardless of insert order, at the cost of ~15-20% overhead on inserts to keep the tree balanced.

2. B-trees are the workhorse of databases. PostgreSQL, MySQL/InnoDB, SQLite, LMDB, MongoDB — every B-tree index in every relational DB you've used is a shallow, wide tree tuned for disk I/O. Instead of 2 children per node, a B-tree node has 100–1000 children, so a table of 1 billion rows is only 3–4 levels deep. That's usually 3–4 disk pages read per lookup — the whole reason WHERE id = ? on an indexed column feels instant even at scale. The Postgres docs linked above are worth 10 minutes of your life.

3. LSM trees (log-structured merge trees) are the write-optimised cousin, powering RocksDB, LevelDB, Cassandra, ScyllaDB, and Kafka's compacted topics. They batch writes to memory, then flush and merge sorted files. Reads may check multiple levels — trading read latency for write throughput. Used everywhere logs and time-series dominate write traffic.

4. Tries and radix trees are trees indexed by string prefixes — powering autocomplete, IP routing tables (longest-prefix match), and file-system path lookups. Redis uses a radix tree for its "stream" data type.

Common bugs and gotchas:

• Corrupting the BST invariant by mutating a node's value in place. If you change a value, you must remove and re-insert.
• Recursive traversal blowing the stack on a very deep tree. Skewed BSTs, pathological XML, or deeply nested JSON can hit 10⁵+ depth. Iterative traversal (with an explicit stack, like your quiz stretch problem) is the fix.
• Rebuilding the whole index instead of just balancing. Some frameworks make it easier to DROP INDEX; CREATE INDEX than to think about maintenance — fine at low scale, catastrophic at high scale (locks, downtime).

The take-away: know that plain BSTs exist mainly as a teaching device; know that balanced trees (RB, B-tree, LSM) are the versions that run the world; and know when reaching for a hashmap vs a tree matters — hashmap is faster for point lookups, tree wins when you also need range queries or ordered iteration.

(e) Quiz + exercise · 10 min

1. State the BST invariant in one sentence.
2. Why does inorder traversal of a BST produce sorted output?
3. What is the worst-case time complexity of search in an unbalanced BST, and when does it happen?
4. Distinguish DFS (preorder / inorder / postorder) from BFS in terms of the auxiliary data structure each uses.
5. Why do relational databases use B-trees (with hundreds of children per node) instead of binary trees for indexes?

Stretch (connects to S024 — Hashmaps): When would you choose a balanced BST (or B-tree) over a hashmap, even though the hashmap has better average-case complexity? Give two concrete scenarios.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Trees & BSTs? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S029): Heaps & Priority Queues
• Previous (S027): Recursion — Call Stack, Base Case, Worked Examples
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.