Lesson 7 of 8 · 50 min

Trees and graphs

Tree BFS/DFS, LCA, graph BFS/DFS, topological sort, clone graph, word ladder — with blast-radius and migration-order production metaphors.

BFS vs DFS is a product decision, not a taste

Builders recurse by habit (call stacks look like DFS) and miss when the question asks for shortest unweighted path or level order — those are BFS. Trees are graphs without cycles; graphs add visited sets, topo order, and clone. Production metaphors: blast radius on service deps (BFS), migration order (topo), recursive JSON AST (DFS), cache-node clone (graph copy).
Tree BFS: queue; level-order, right side view, zigzag, min depth. Tree DFS: pre/in/post; path sum, LCA, serialize/deserialize, diameter. Graph BFS: shortest path in unweighted graph / word ladder. Graph DFS: components, cycle in undirected, path existence. Topo sort: Kahn (BFS indegree) or DFS finish times — course schedule. Clone graph: map old→new while DFS/BFS.
Complexity: tree n nodes O(n); graph O(V+E). State both. Visited must be said for graphs or you infinite-loop on cycles. For trees, null base cases are Verification freebies — hit them in dry-run.

Tree BFS: level order and right side view

python
1LEVEL ORDER — template for tree BFS23from collections import deque45def level_order(root):6    if not root:7        return []8    q = deque([root])9    out = []10    while q:11        level = []12        for _ in range(len(q)):13            node = q.popleft()14            level.append(node.val)15            if node.left: q.append(node.left)16            if node.right: q.append(node.right)17        out.append(level)18    return out1920# Right side view: last node in each level (or track right-first DFS with depth).

Tree DFS: path sum and LCA sketch

Path sum: recurse remaining target, careful with leaf definition. LCA in BST: use value ordering; LCA in binary tree: recurse and combine (if both sides non-null, root is LCA). Serialize: preorder with null markers; deserialize with iterator. Production: AST walk for a rules engine — same DFS skeleton.
python
1LCA OF BST — exploit ordering23def lca_bst(root, p, q):4    while root:5        if p.val < root.val and q.val < root.val:6            root = root.left7        elif p.val > root.val and q.val > root.val:8            root = root.right9        else:10            return root11    return None1213# O(h) time, O(1) space iterative — mention vs recursive O(h) stack.

Graph: course schedule (topo) and clone

python
1COURSE SCHEDULE — Kahn topo; cycle ⇒ false23from collections import deque, defaultdict45def can_finish(num_courses: int, prereq: list[list[int]]) -> bool:6    graph = defaultdict(list)7    indeg = [0] * num_courses8    for a, b in prereq:  # b -> a (b before a)9        graph[b].append(a)10        indeg[a] += 111    q = deque([i for i in range(num_courses) if indeg[i] == 0])12    seen = 013    while q:14        u = q.popleft()15        seen += 116        for v in graph[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return seen == num_courses2122# Production: migration order of services; cycle = deploy deadlock.
python
1CLONE GRAPH — map original node -> clone23def clone_graph(node):4    if not node:5        return None6    mp = {}7    def dfs(n):8        if n in mp:9            return mp[n]10        copy = Node(n.val)11        mp[n] = copy12        for nei in n.neighbors:13            copy.neighbors.append(dfs(nei))14        return copy15    return dfs(node)1617# O(V+E). Bug: cloning without map → infinite recursion on cycles.

Word ladder — BFS shortest transformation

Each word is a node; edge if one letter differs. BFS from beginWord to endWord; level depth is ladder length. Optimize with wildcard pattern map (*ot → [hot,dot,…]). DFS can find a path but not efficiently the shortest — say why BFS wins on unweighted edges.

Word ladder mechanics and grid-as-graph

Build adjacency carefully: O(word_len * 26 * dict) with wildcard buckets beats O(n²) pairwise checks for large dictionaries. BFS stores distance or level size; first time you pop endWord you return steps. Bidirectional BFS is a senior follow-up — mention if time allows, implement only if asked.
Grids (islands, rotting oranges, walls and gates) are graphs with 4-neighbor edges. Same BFS/DFS choice rules apply. Multi-source BFS (all rotten oranges in queue at t=0) is a production cousin of “all alerts fire, expand impact fronts together.” Name multi-source when the prompt has many starts.
python
1WORD LADDER — BFS with pattern map (sketch)23from collections import defaultdict, deque45def ladder_length(begin: str, end: str, word_list: list[str]) -> int:6    if end not in word_list:7        return 08    buckets: dict[str, list[str]] = defaultdict(list)9    for w in word_list:10        for i in range(len(w)):11            buckets[w[:i] + "*" + w[i+1:]].append(w)12    q = deque([(begin, 1)])13    seen = {begin}14    while q:15        w, d = q.popleft()16        if w == end:17            return d18        for i in range(len(w)):19            for nei in buckets[w[:i] + "*" + w[i+1:]]:20                if nei not in seen:21                    seen.add(nei)22                    q.append((nei, d + 1))23    return 0

Serialize and path problems — DFS discipline

Serialize/deserialize: pick a scheme (preorder with null tokens is common), write both directions, dry-run a 3-node tree. Path sum II (all root-to-leaf paths): backtracking on trees — append/pop values. Diameter: height postorder returning height while updating global best left_h+right_h. These are Verification-heavy: one wrong base case fails all.
Course Schedule / Graph overview style (NeetCode graph playlist)NeetCode

Interview prep

Tree/graph rounds are classification drills under the clock. Practice saying BFS/DFS/topo in the first 30 seconds of three random prompts.
  1. 01“BFS vs DFS?” → layers/shortest unweighted → BFS; paths/subtrees/backtrack → DFS.
  2. 02“Course schedule?” → topo Kahn; if not all nodes processed, cycle.
  3. 03“Clone graph?” → map old→new; DFS or BFS; without map infinite loop.
  4. 04“Word ladder?” → BFS on word graph; each edge one letter change.
  5. 05“LCA BST vs binary tree?” → BST walk by value; tree needs postorder combine.
  6. 06“Complexity graph?” → O(V+E) time; space O(V) for queues/visited.
  7. 07“Serialize tree?” → preorder + null markers; or level order with nulls.
  8. 08“Production?” → blast radius BFS; migration topo; AST DFS; graph clone for configs.
  9. 09"Course schedule cycle?" -> Kahn processed < V, or DFS gray back-edge.
  10. 10"Clone graph key?" -> map original -> clone during BFS/DFS.
  11. 11"UF when?" -> dynamic connectivity, redundant edges, accounts merge, provinces.
  12. 12"Tree diameter?" -> two BFS or height DP; path through root vs subtrees.
  13. 13"Level-order trick?" -> snapshot len(q) before processing a level.
  14. 14"When BFS not Dijkstra?" -> unweighted (or equal weight) edges only.
docsNeetCode — Graph algorithms practiceNeetCodearticleTIH — GraphsTech Interview HandbookarticleTIH — TreesTech Interview HandbookarticleAlgoMaster — Tree/Graph patternsAlgoMaster

Topo, union-find, and traversal spoken catalog

Trees: BFS level-order (capture len(q)); DFS depth/diameter/path sums; validate BST with (min,max) window; LCA BST walk vs BT recurse. Graphs: islands flood/UF; clone graph (map original->clone is the insight); course schedule Kahn/colors; word ladder BFS; bipartite coloring. UF: provinces, redundant connection, accounts merge. Production: org charts, crawlers, Bazel/Airflow/Make topo, account de-dupe, social BFS. Always visited on graphs; white/gray/black for directed cycles; parent skip on undirected. For every tree problem, say null base first. For every graph problem, say visited first. Level-order: snapshot queue length before the inner loop. Diameter is max over all nodes of left_height+right_height, not only at root — DFS returning height while updating a global best is the clean pattern. Islands: DFS shortest code; UF if the grid streams. Clone graph fails without the map. Course schedule is Kahn or gray-node DFS; defend O(V+E). Drill set for the week: invert binary tree, level order, validate BST, LCA BT, number of islands, clone graph, course schedule, redundant connection — eight problems, each narrated against the four axes, not just coded. Time-box 20 minutes each. If you skip naming BFS vs DFS in the first minute, mark Communication down deliberately so the habit forms. For UF, implement find and union without looking once; path compression is one line that interviewers watch for. Dijkstra is optional for most product loops but required if the company posts weighted graph tags — know when BFS is wrong (non-unit weights).
python
1COURSE SCHEDULE — Kahn topo (cycle => False)23from collections import deque, defaultdict45def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:6    graph: dict[int, list[int]] = defaultdict(list)7    indeg = [0] * num_courses8    for a, b in prerequisites:  # b -> a9        graph[b].append(a)10        indeg[a] += 111    q = deque([i for i in range(num_courses) if indeg[i] == 0])12    seen = 013    while q:14        u = q.popleft()15        seen += 116        for v in graph[u]:17            indeg[v] -= 118            if indeg[v] == 0:19                q.append(v)20    return seen == num_courses  # incomplete => cycle; O(V+E)
python
1UNION-FIND — path compression + union by rank23class DSU:4    def __init__(self, n: int):5        self.p = list(range(n))6        self.r = [0] * n78    def find(self, x: int) -> int:9        while self.p[x] != x:10            self.p[x] = self.p[self.p[x]]11            x = self.p[x]12        return x1314    def union(self, a: int, b: int) -> bool:15        ra, rb = self.find(a), self.find(b)16        if ra == rb:17            return False  # redundant edge18        if self.r[ra] < self.r[rb]:19            ra, rb = rb, ra20        self.p[rb] = ra21        if self.r[ra] == self.r[rb]:22            self.r[ra] += 123        return True  # ~O(alpha(n)) amortized
Graders + tiers. Name BFS/DFS/topo/UF before code. Unweighted shortest = BFS; weighted = Dijkstra. Null base + visited. Verify 1-node, disconnected, self-loop. FAANG mixes patterns. India OA: tree height/diameter/LCA more than heavy graphs. AI lab: tool DAGs, cycle detection, clone structures. Skewed trees blow recursion depth at 1e5 — mention iterative DFS if constraints are huge. William Fiset graph playlist and TIH tree/graph cheatsheets are the free spine; NeetCode trees+graphs for LC coverage. Add one Union-Find implementation from blank memory every other day until path compression is automatic. For trees, alternate recursive and iterative DFS so a 1e5-skewed constraint does not panic you mid-round. Before the onsite week, run one full mock that mixes a tree LCA with a course-schedule graph so you practice re-classifying families under fatigue. Name the algorithm in the first thirty seconds every time — graders write that phrase into the packet, so make it easy to quote in the written debrief form later on.
Course Schedule — NeetCodeNeetCodeUnion-Find — William FisetWilliam FisetarticleGraph cheatsheet — TIHTech Interview Handbook

Checkpoint

Shortest transformation from word A to B in a dictionary (one letter per step). Algorithm?

ADFS recursion trying all letters — return first path foundBBFS from A; each edge one-letter mutation; first time you reach B is minimum stepsCBinary search on word list
Sign up free to answer and see why

Checkpoint

Service dependency graph, directed. Need deploy order so deps go first. Cycle possible. Tool?

ATree level order onlyBTopological sort (Kahn); if processed count < V, report cycle / refuse deployCDijkstra with random weights
Sign up free to answer and see why

Checkpoint

Clone graph complexity with V vertices E edges?

AO(V²) alwaysBO(V+E) time and O(V) space for the map + outputCO(1) time if you shallow copy the list
Sign up free to answer and see why

Checkpoint

Right side view of a binary tree — clean approach?

AOnly print root.right chainBBFS level order; record last node per level (or DFS depth-first preferring right)CInorder traversal list mid element
Sign up free to answer and see why

Checkpoint

Interviewer: min depth of binary tree. You DFS full height of both sides always. Issue?

ANo issue — always optimalBBFS to first leaf is often clearer O(n) with early exit; full DFS is correct but may do more work on unbalanced trees in practice — mention bothCMust use Dijkstra
Sign up free to answer and see why

Can you choose BFS/DFS/topo on a fresh prompt and implement clone graph without infinite recursion?

New to itGetting thereConfident

Takeaways

  • BFS for layers and unweighted shortest paths; DFS for structure/paths.
  • Topo (Kahn) for ordering with cycle detection.
  • Clone = map old→new while traversing.
  • Word ladder is BFS on an implicit graph.
  • Always state O(V+E) and visited policy on graphs.

Next: DP, backtracking, and the capstone mock — LRU, token bucket, streaming median under the four-axis rubric.

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with EnzoSign up free