Lesson 25 · Trees & graphs

Trees — beyond traversal

📖 Walk me through it — plain English

A tree is data shaped like a family tree: one top item (the root), and every item can point down to children. An item with no children is a leaf. A binary tree means each item has at most two children — a left and a right. A subtree is just any node together with everything hanging below it.

This lesson goes past simply visiting every node. It shows four moves interviewers love: a BST (Binary Search Tree — a binary tree kept sorted so every left subtree is smaller than the node and every right subtree is larger), Tree DP (solve the children first, then combine their answers at the parent — DP just means "reuse smaller answers"), LCA (Lowest Common Ancestor — the deepest node that has both target nodes below it), and serialize/deserialize (flatten a tree to a string and rebuild it).

The reusable trick is the postorder return in the diameter code: a function asks each child "how deep are you?", and only after both answers come back does it do its own work. Postorder = left, then right, then me. Think of a manager who waits for both team members to finish before reporting up — nobody reports until those under them have.

Let's trace diameter (the longest chain of edges between any two nodes) on this tiny tree. depth(n) returns 1 + the deeper child's depth. As it goes, it updates best with l + r — the number of edges in a path passing straight through node n. The cells below are the call stack and the running best.

Tree: root A has left B and right C; B has left D. So A-B-D is a chain of 2 edges, plus A-C.

Step 1 · Recurse all the way down-left first. We reach D's children, which are empty (null). An empty spot returns depth 0. best so far = 0.

Step 2 · D is a leaf: l=0, r=0. Update best = max(0, 0+0) = 0. D returns 1 + max(0,0) = 1 up to B.

D=1

best 0

Step 3 · Back at B: left child D gave l=1, right child is empty so r=0. Update best = max(0, 1+0) = 1. B returns 1 + max(1,0) = 2 up to A.

B=2

l 1

r 0

best 1

Step 4 · A's right child C is a leaf and returns 1 (same logic as D). Now A has l=2 (from B) and r=1 (from C). Update best = max(1, 2+1) = 3.

l 2

r 1

best 3

Answer · The longest path is D-B-A-C, which is 3 edges. best = 3.

Why it works: the longest path either passes through a node (its left depth + right depth, which is exactly the l + r we check at every node) or lives entirely inside one subtree (caught when we visit that subtree). By checking l + r at every single node and keeping the max in best, we cover all cases. Because each node is visited once and does O(1) work, the whole thing is O(n) time. The same shape — recurse, get child answers, combine, then return one value upward — solves LCA, max-path-sum, and most "longest/biggest in a tree" questions.

BSTs, LCA, tree DP, serialize/deserialize. A common interview ladder you can't skip.

Visual — Binary Search Tree

BST invariant: every left subtree < node < every right subtree.

Traversals

Preorder: root, left, right — clone tree
Inorder: left, root, right — sorted output for BST
Postorder: left, right, root — delete tree, tree DP
Level-order: BFS — shortest path, "by row" queries

BST operations

Search/insert: O(h) — h ≈ log n if balanced
Delete: 3 cases (leaf, one child, two children → swap with in-order successor)
Validate: in-order must be strictly increasing
Worst case (degenerate chain): O(n) — that's why AVL / Red-Black exist

Pattern · Tree DP (postorder return)

Process children first, combine results at the parent. Most "max path / diameter / longest sequence" tree problems are this.

def diameter(root):
    best = [0]
    def depth(n):
        if not n: return 0
        l = depth(n.left)
        r = depth(n.right)
        best[0] = max(best[0], l + r)   # path THROUGH this node
        return 1 + max(l, r)               # path FROM this node up
    depth(root)
    return best[0]

Pattern · LCA (Lowest Common Ancestor)

def lca(root, p, q):
    if not root or root is p or root is q:
        return root
    l = lca(root.left, p, q)
    r = lca(root.right, p, q)
    if l and r: return root   # found in both subtrees → root is LCA
    return l or r

For repeated queries, use binary lifting: precompute 2^k ancestors per node in O(n log n); each query is O(log n).

Pattern · Serialize / Deserialize

# Preorder with sentinels for null
def serialize(root):
    out = []
    def go(n):
        if not n: out.append("#"); return
        out.append(str(n.val)); go(n.left); go(n.right)
    go(root); return ",".join(out)

def deserialize(s):
    it = iter(s.split(","))
    def go():
        v = next(it)
        if v == "#": return None
        n = TreeNode(int(v))
        n.left = go(); n.right = go()
        return n
    return go()

Interactive — step through tree traversals

Pick an order, then step.

Maximum depth of a binary tree — one recursive line after the base case:

→ Going deeper: Tree problems are graph problems on acyclic connected components. See BFS / DFS.