Trees & BSTs

01Why hierarchy at all?

Arrays and lists are linear — great for sequences, terrible for representing "contains" / "reports to" / "is a subdirectory of." Trees exist because a huge amount of real data is hierarchical: file systems, JSON documents, the DOM, org charts, ASTs (every LLM-generated code snippet you've ever parsed), Kubernetes object ownership. A tree is the honest shape of that data.

But there's a second, sneakier reason: a balanced tree turns O(n) into O(log n). If each step down the tree discards half the remaining data, n items are only log₂(n) levels deep. That "hierarchy as a search accelerator" idea is the entire reason BSTs, heaps, and database indexes exist.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

            [8]              height 2, 7 nodes
           /   \             every subtree is a tree →
        [3]     [10]         recursion is not a trick here,
        / \        \         it's the structure talking
     [1]  [6]      [14]

02Traversals — the four ways to visit everything

"Traversal" = visit every node once. The only question is order. Three are DFS (go deep first), one is BFS (go wide first). How to remember which is which: "pre / in / post" says where the root goes relative to its children.

Any time a node's answer depends on its children's answers, you're doing postorder whether you call it that or not.

Recursive DFS — the 4-line version

def inorder(node, out):
    if not node:
        return
    inorder(node.left, out)
    out.append(node.val)          # move this line up/down for pre/post
    inorder(node.right, out)

That comment is the whole story: the three DFS orders are one function with the "visit" line in three positions. Before the recursions = preorder; between = inorder; after = postorder.

Iterative versions (know at least these two)

Recursion uses the call stack; iterative versions use an explicit stack. Interviewers ask for them to (a) test stack understanding, (b) dodge Python's ~1000-frame recursion limit.

Iterative preorder — the easy one:

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # right first...
        if node.left:  stack.append(node.left)    # ...so left pops first
    return out

Iterative inorder — the important one (it's how you build a BST iterator):

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                 # slide as far left as possible
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()          # leftmost unvisited
        out.append(cur.val)
        cur = cur.right            # then explore its right subtree
    return out

Level-order (BFS) — a queue, and a per-level size counter:

from collections import deque
def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):        # freeze current level size
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

The for _ in range(len(q)) trick — snapshotting the queue length to delimit a level — is the detail that separates "knows BFS" from "has written BFS."

Complexities

"DFS costs height, BFS costs width" is a tidy sentence to deploy. h = log n balanced, n degenerate.

def solve(node):
    if node is None:
        return BASE                 # the empty tree's answer
    left  = solve(node.left)        # trust the recursion (leap of faith)
    right = solve(node.right)
    return combine(left, right, node)

03Binary Search Trees

The BST invariant: for every node, everything in the left subtree < node.val < everything in the right subtree. Not just the children — the entire subtrees.

Why that invariant is money: at each node you can discard half the tree. Search, insert, delete — all O(h), which is O(log n) if the tree is balanced.

def search(node, target):
    while node:
        if target == node.val: return node
        node = node.left if target < node.val else node.right
    return None

It's binary search with pointers — same halving, but insertions don't require shifting an array. That's the point of a BST: a sorted collection that stays cheap to modify.

Validate BST — the trap question

        [5]
       /   \
     [3]   [8]
           /
         [4]    ← 4 < its parent 8, fine? No! 4 sits in 5's RIGHT
                  subtree, so it must be > 5. Local checks miss
                  violations of ancestor bounds.

Two correct approaches:

# 1. Pass down valid (lo, hi) bounds — each edge tightens one bound
def is_valid(node, lo=float('-inf'), hi=float('inf')):
    if not node:
        return True
    if not (lo < node.val < hi):
        return False
    return (is_valid(node.left,  lo, node.val) and
            is_valid(node.right, node.val, hi))

# 2. Inorder traversal must be strictly increasing (check on the fly, O(h) space)

Going left tightens the upper bound to the parent's value; going right tightens the lower bound. A node is valid only inside the window every ancestor has carved out for it.

04Lowest Common Ancestor — both variants

In a BST — the invariant does all the work. Walk from the root: if both targets are smaller, go left; both bigger, go right; otherwise you're standing on the split point — that's the LCA:

def lca_bst(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:   node = node.left
        elif p.val > node.val and q.val > node.val: node = node.right
        else: return node        # p and q diverge here (or one equals node)
    return None

In a general binary tree — no ordering to steer by, so recurse both sides: "the LCA is the first node where p and q appear in different subtrees (or the node itself is one of them)":

def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left  = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root              # p and q split here
    return left or right         # both are on one side (or neither found)

One sentence for the interview: the BST version is O(h) and iterative because ordering tells you which way to walk; the general version must explore both subtrees and returns the node where both searches come back non-empty.

05Serialize / Deserialize

"Turn a tree into a string and back" — i.e., write a codec. The clean answer: preorder with explicit null markers. The nulls are what make the shape unambiguous (without them, one value sequence maps to many trees).

def serialize(root):
    out = []
    def dfs(node):
        if not node:
            out.append("#")
            return
        out.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ",".join(out)          # e.g. "8,3,1,#,#,6,#,#,10,#,14,#,#"

def deserialize(data):
    vals = iter(data.split(","))
    def build():
        v = next(vals)
        if v == "#":
            return None
        node = TreeNode(int(v))
        node.left = build()       # preorder: consume tokens in the same order
        node.right = build()
        return node
    return build()

06Balance: the BST's Achilles heel, and the fix

Insert 1, 2, 3, 4, 5 into an empty BST in order and every "left" is empty. Height = n. Search is now O(n) — you built an expensive linked list. Sorted (or nearly sorted) input is common in real systems — auto-increment IDs, timestamps — so this isn't a corner case.

Self-balancing trees fix it by doing small local repairs — rotations — on insert/delete to keep height O(log n). A rotation, in one picture — an O(1) pointer swap that shifts height between siblings while preserving the BST ordering:

      [3]                     [2]
      /        rotate         /  \
    [2]       ───────►      [1]  [3]
    /          right
  [1]

07B-trees — why databases don't use binary trees

Here's the part that connects to your day job. Postgres indexes are B-trees (B+ trees, precisely). Why not a red-black tree?

Because the bottleneck isn't comparisons — it's I/O. A disk (or even a page cache miss) hands you data in fixed-size pages (Postgres: 8 KB). Fetching a page costs the same whether you use 16 bytes of it or all 8 KB. A binary tree node uses one key per hop ⇒ one page fetch per level ⇒ ~30 fetches for a billion rows. Wasteful.

A B-tree node fills the whole page with keys — hundreds of them — so each fetch narrows the search by a factor of hundreds, not 2:

Binary tree (fanout 2):              B-tree (fanout ~300):
depth for 10⁹ keys ≈ 30              depth for 10⁹ keys ≈ log₃₀₀(10⁹) ≈ 3-4
30 page reads                        3-4 page reads (root usually cached → ~2)

B-tree node = one disk page:
┌──────────────────────────────────────────────┐
│ k₁ k₂ k₃ ... k₂₉₉        (sorted keys)       │
│ ↓  ↓  ↓  ...  ↓   ↓      (300 child ptrs)    │
└──────────────────────────────────────────────┘
  within a node: binary search the keys (in RAM — comparisons are free now)

• Nodes stay between half-full and full; when a node overflows, it splits and promotes its middle key upward — trees grow up from the leaves, staying perfectly balanced by construction.
• B+ tree refinement: all values live in the leaves; leaves are chained left-to-right in a linked list — which makes range scans (WHERE created_at BETWEEN ..., ORDER BY ... LIMIT) a sequential walk along the leaf level. That leaf chain is why your indexed range queries are fast.

08Common interview questions

09Self-test