Trees and graphs: traversals, BFS and DFS, topological sort, union-find, Dijkstra

Before this lesson: lesson 01 (hash sets, two pointers) and lesson 02 (stack, queue, binary search, heap). Time: about 95 minutes, plus the notebook. This is a long lesson: you can stop after section "Lowest common ancestor" and continue with graphs later.

---

Why this matters #

Graph and tree problems are the most common "medium" problems in coding rounds. They test one skill: turn the story into nodes and edges, then pick the right template. Almost every problem uses one of six templates (tree recursion, BFS, DFS, topological sort, union-find, Dijkstra), and each one runs in linear or near-linear time in 15–30 lines.

The same structures are daily tools in ML. Autograd runs the backward pass in reverse topological order of the computation graph (Calculus lesson 05). A decision tree predicts with one root-to-leaf walk. Graph neural networks pass messages along edges (Deep Learning lesson 13): after $k$ layers, a node sees exactly its BFS ball of radius $k$. A data pipeline with dependencies is a directed acyclic graph, and a scheduler runs it in topological order.

Notation. $n$ is the number of nodes of a tree, $h$ its height and $w$ its width (the largest number of nodes on one level). For a graph, $V$ and $E$ are the sets of nodes and edges, and also their sizes.

1. Predict first #

2. The picture #

Trees: solve left, solve right, combine #

A binary tree is either empty, or a node with a value and two children, left and right, that are binary trees themselves. The top node is the root; a node without children is a leaf. A tree with $n$ nodes has $n - 1$ edges, because every node except the root has exactly one parent. The depth of a node is the number of edges from the root to it, and the height $h$ of the tree is the largest depth. A path of $n$ nodes has $h = n - 1$; a balanced tree has $h \approx \log_2 n$.

Because the definition is recursive, most tree code is recursive too: answer the question for the left subtree, answer it for the right subtree, combine the two answers at the node. The empty tree is the base case. A traversal visits every node once. Depth-first traversals differ only in when the node itself is visited:

Traversal	Order	Typical use
pre-order	node, left, right	copy or serialize a tree
in-order	left, node, right	a binary search tree in sorted order
post-order	left, right, node	combine the children's answers: height, diameter, LCA
level order (BFS)	level by level, with a queue	anything "per level", the nearest leaf

Interactive figure: loading…

Graphs: one loop, three bags #

A graph $G = (V, E)$ has a set $V$ of nodes and a set $E$ of edges. An edge is directed ($u \to v$) or undirected ($u - v$), and it may carry a weight $w(u, v)$. A tree is a connected undirected graph without a cycle. In a general graph you can arrive at a node again by another path, so every search keeps a visited set.

You must choose how to store the graph. In interviews it is almost always an adjacency list.

Representation	Memory	Neighbours of $u$	Good for
adjacency list (list of lists, or dict)	$O(V + E)$	$O(\deg u)$	almost everything
adjacency matrix	$O(V^2)$	$O(V)$	dense graphs, $O(1)$ edge test
edge list	$O(E)$	—	Kruskal, union-find, Bellman-Ford
implicit (computed when needed)	nothing stored	depends	grids, word ladders, puzzle states

Here $\deg u$ is the degree of $u$, its number of neighbours. Jeff Erickson calls the next loop whatever-first search: keep a bag of nodes to visit; take one out; if it is new, mark it and put its neighbours in the bag. Only the type of bag changes:

put s in the bag
while the bag is not empty:
    take v out of the bag
    if v is not marked:
        mark v                       # v is now visited
        for each neighbour u of v:
            put u in the bag

• bag = stack (last in, first out) → depth-first search (DFS): go deep first, back up when stuck;
• bag = queue (first in, first out) → breadth-first search (BFS): all nodes at distance 1, then 2, …;
• bag = priority queue keyed by the distance so far → Dijkstra's algorithm (keyed by the weight of the last edge → Prim's minimum spanning tree).

Interactive figure: loading…

3. Definitions and main results #

Traversals and their cost #

Each traversal visits every node once and does $O(1)$ work per node: $O(n)$ time. The extra memory differs:

• Depth-first (pre, in, post), recursive or with an explicit stack, keeps the current path from the root: at most $h + 1$ nodes, so $O(h)$ extra space. This is $O(\log n)$ for a balanced tree and $O(n)$ for a path.
• Level order keeps one level (and part of the next) in a queue: $O(w)$. A complete tree has about $n/2$ leaves on its last level, so $w \approx n/2$.

So for a balanced tree DFS needs much less memory than BFS, and for a long path the opposite is true. In Python, use collections.deque and popleft() for the queue: list.pop(0) costs $O(n)$ per pop. Recursion fails beyond about 1,000 levels (sys.getrecursionlimit()), so on deep trees use an explicit stack (the iterative in-order code is in section 5).

The post-order template. A function returns one value per subtree (its height, its sum, "does it contain $p$?"), computed from the values of its two children. If the answer is a path that turns at a node, such as the diameter (the longest path between two nodes), the function returns the best path going down, and a separate variable keeps the best turning path: at each node, update best = max(best, height(left) + height(right) + 2) with height $-1$ for an empty subtree.

Binary search trees #

A binary tree is a binary search tree (BST) (strict: no equal values) if at every node, all values in the left subtree are smaller than the node's value and all values in the right subtree are larger. A search walks one path down, like binary search in a sorted array.

Theorem 1. A binary tree is a BST if and only if its in-order sequence is strictly increasing.

Proof (induction on the number of nodes; the empty tree is a BST with an empty sequence).

1. For a root value $v$ with left subtree $L$ and right subtree $R$, the in-order sequence is $\text{in}(L)$, then $v$, then $\text{in}(R)$.
2. If the tree is a BST, so are $L$ and $R$. By induction $\text{in}(L)$ and $\text{in}(R)$ increase. All of $\text{in}(L)$ is below $v$ and all of $\text{in}(R)$ is above $v$, so the whole sequence increases.
3. If the sequence strictly increases, every value of $L$ is below $v$, every value of $R$ is above $v$, and $\text{in}(L)$ and $\text{in}(R)$ increase. By induction $L$ and $R$ are BSTs, so the tree is a BST. $\blacksquare$

Validate with intervals, not with the children. A common bug compares each node only with its parent. Take root 5 with left child 3 and right child 8, and give 3 a right child 6. Every parent–child pair looks correct ($3 < 5$, $8 > 5$, $6 > 3$), but 6 is in the left subtree of 5, so the tree is not a BST. The in-order sequence $3, 6, 5, 8$ shows it. The fix: pass down an open interval $(low, high)$. The root gets $(-\infty, +\infty)$; going left from value $v$ sets $high = v$, going right sets $low = v$. Node 6 gets $(3, 5)$ and fails. Use math.inf or None for the open ends, never a "large number" such as $2^{31}$.

Cost. Search and insertion walk one path: $O(h)$. If you insert keys in random order, $h$ stays $O(\log n)$ on average; if you insert sorted keys, the tree becomes a path with $h = n - 1$. Balanced trees (AVL, red-black) keep $h = O(\log n)$ always.

Lowest common ancestor #

The lowest common ancestor (LCA) of nodes $p$ and $q$ is the deepest node that has both of them in its subtree. A node is in its own subtree, so the LCA of $p$ and a descendant of $p$ is $p$.

Theorem 2 (LCA in a BST). Let $p \le q$ be values in the BST. Start at the root. Go left while both values are smaller than the node, go right while both are larger, and stop otherwise. The stop node is the LCA. Time $O(h)$, extra space $O(1)$.

Proof.

1. Invariant: $p$ and $q$ are in the subtree of the current node. It holds at the root. If both values are smaller than the node, the BST order puts both in the left subtree; the same holds on the right. So every move keeps the invariant.
2. At the stop node $v$ we have $p \le v \le q$. If $v$ equals $p$ or $q$, the other one is in its subtree (invariant), so $v$ is the LCA.
3. Otherwise $p < v < q$: $p$ is in the left subtree and $q$ in the right one. No child of $v$ contains both, so $v$ is the deepest node that does. $\blacksquare$

In a general binary tree (both nodes present), use the post-order template. The function returns None if the subtree contains neither node. At $p$ or $q$ it returns that node. If both children return a node, the current node is the LCA; otherwise it passes up the one result. Time $O(n)$, space $O(h)$.

Serialization with null markers, and tries #

To serialize a tree is to write it as a string from which the same tree can be rebuilt. Write the pre-order, with a marker # for every missing child and a separator between tokens (so that 1,11 cannot be read as 11). Example: root 1 with children 2 and 3 gives 1,2,#,#,3,#,#.

Theorem 3. (a) The string of a tree with $n$ nodes has exactly $n + 1$ markers. (b) Different trees give different strings.

Proof of Theorem 3

1. (a) For $n \ge 1$, the $n$ nodes have $2n$ child places. Every node except the root fills one place, so $n - 1$ places are filled and $n + 1$ are empty, one marker each. The empty tree ($n = 0$) is the single marker #.
2. (b) Parse a string like this: read the next token; for # return the empty tree; otherwise create a node with that value, then parse its left subtree, then its right subtree.
3. By induction on the size of a tree $T$: given the string of $T$ followed by any text, the parser returns $T$ and stops exactly at the end of the string of $T$. (It reads the root token, then by induction exactly the left subtree, then exactly the right one.)
4. If two trees $T_1$ and $T_2$ had the same string $s$, both would equal the parser's output on $s$, so $T_1 = T_2$. $\blacksquare$

Without markers, pre-order is ambiguous: 1, 2 can be root 1 with a left child 2 or with a right child 2. In-order alone is also ambiguous. Pre-order plus in-order fixes a tree with distinct values ("Construct Binary Tree from Preorder and Inorder Traversal").

A trie (prefix tree) stores strings: each edge adds one character, so each node is a prefix. A node has a dict children and a flag is_word. The words to, tea, ted, ten, i, in, inn need 10 nodes: the root (the empty prefix) and t, to, te, tea, ted, ten, i, in, inn. For a word or prefix of length $L$, insert and search cost $O(L)$, and the question "does any word start with this prefix?" also costs $O(L)$. With a Python set of $N$ words that question needs a scan of all words, $O(NL)$. A search must check is_word at the last node: te is a prefix, not a word.

BFS finds shortest paths in unweighted graphs #

In BFS, set $\text{dist}[s] = 0$; when $u$ is taken out of the queue and a neighbour $v$ is not yet visited, set $\text{dist}[v] = \text{dist}[u] + 1$, mark $v$ as visited at once, and append it to the queue. Let $\delta(v)$ be the true fewest-edges distance from $s$.

Theorem 4 (BFS). Every node $v$ that is reachable from $s$ gets $\text{dist}[v] = \delta(v)$.

Proof.

1. Every dist value is the length of a real path from $s$ (follow the nodes that discovered each other back to $s$). So $\text{dist}[v] \ge \delta(v)$.
2. The queue always holds dist values in non-decreasing order, and the first and last differ by at most 1. Taking out a node with value $d$ and appending nodes with value $d + 1$ keeps this true. So nodes leave the queue in non-decreasing order of dist.
3. Induction on $k = \delta(v)$; for $k = 0$, $v = s$. For $k \ge 1$, let $u$ be the node before $v$ on a shortest path, so $\delta(u) = k - 1$ and, by induction, $\text{dist}[u] = k - 1$. If $v$ is not yet visited when $u$ is taken out, it gets $k$. If it was discovered earlier, its discoverer left the queue no later than $u$, so by step 2 it has dist $\le k - 1$, which gives $\text{dist}[v] \le k$. With step 1, $\text{dist}[v] = k$. $\blacksquare$

Cost. Because a node is marked when it is put in the queue, each node enters the queue once, and each adjacency list is read once: $O(V + E)$ time, $O(V)$ extra memory. If you mark only when a node is taken out, the same node can enter the queue once per edge into it. (The figure uses Erickson's general loop, which marks when a node is taken out and skips nodes that are already marked. This is also correct, but the bag can grow to $O(E)$ entries; the "skipped" counter shows those extra entries.)

DFS goes deep first and backs up when stuck. It finds a path, not a shortest one. Use it for reachability, connected components, flood fill, cycle detection and topological order. In Python, write it with a list as an explicit stack: one island in a $150 \times 150$ grid can have more than 10,000 cells, far beyond the recursion limit.

Two BFS variants appear often in interviews:

• Multi-source BFS: put all sources in the queue at distance 0, as if one extra source were joined to all of them. Use it for "distance to the nearest X" and for "Rotting Oranges" (all rotten oranges spread at the same time; the answer is the largest distance).
• Grids as implicit graphs: each cell is a node with up to 4 neighbours. "Number of Islands" counts connected components: scan the cells, and start a BFS or DFS from every land cell that is not yet visited. Cost $O(RC)$ for $R$ rows and $C$ columns.

Two more BFS variants

• 0-1 BFS. If every weight is 0 or 1, use a deque: push a node to the front after a 0-edge and to the back after a 1-edge. The deque stays sorted by distance, as in step 2 of the proof, and the cost stays $O(V + E)$.
• Bidirectional BFS. Search from both ends and stop when the two frontiers meet. With branching factor $b$ and distance $d$, it explores about $2b^{d/2}$ nodes instead of $b^d$ ("Word Ladder").

Topological sort #

A topological order of a directed graph lists the nodes so that every edge $u \to v$ has $u$ before $v$. It exists if and only if the graph has no directed cycle, that is, if it is a directed acyclic graph (DAG). The in-degree of a node is the number of edges that come into it.

Kahn's algorithm. Count the in-degree of every node. Put all nodes of in-degree 0 in a queue. Repeat: take a node out, append it to the output, and decrease the in-degree of each successor by 1; when a successor's in-degree reaches 0, put it in the queue. Cost $O(V + E)$.

Theorem 5 (Kahn). Kahn's algorithm outputs all $V$ nodes if and only if the graph is a DAG, and then the output is a topological order.

Proof.

1. Order. A node enters the queue only when its in-degree reaches 0, that is, after all its predecessors were output. So every edge $u \to v$ has $u$ before $v$.
2. A cycle gives a short output. On a directed cycle, every node has a predecessor on the cycle that must be output first. No node of the cycle can be first, so none of them is ever output.
3. A DAG gives the full output. While nodes remain, the remaining graph is still a DAG, so it has a node of in-degree 0. (Otherwise walk backwards along incoming edges: with finitely many nodes the walk repeats a node, and that is a cycle.) That node is in the queue, so the algorithm does not stop early. $\blacksquare$

So the cycle test is one line: len(order) < V means there is a cycle.

Interactive figure: loading…

Kahn by levels. If each round takes out the whole current queue, the rounds are the batches of tasks that can run in parallel, and the number of rounds equals the number of nodes on the longest path. ("Parallel Courses" asks for this number.)

The DFS version. Run DFS and record each node when it finishes (after all its successors). The reverse of the finishing order is a topological order. For cycle detection, DFS needs three colours: white (not seen), grey (on the current DFS path) and black (finished). An edge to a grey node closes a cycle. Two colours are not enough: in the "diamond" $0 \to 1 \to 3$, $0 \to 2 \to 3$, node 3 is reached twice without any cycle.

Union-find #

Union-find (also called disjoint set union, DSU) keeps a partition of the elements $0, \dots, n-1$ into disjoint sets. find(x) returns the representative (the root) of the set of $x$; union(a, b) merges the sets of $a$ and $b$. The sets are stored as a forest of parent pointers; a root points to itself. Two rules make it fast:

• Union by rank: put the root of smaller rank under the root of larger rank. On a tie, put the root of $b$ under the root of $a$ and increase the rank of $a$'s root by 1. The rank is an upper bound on the height of the tree.
• Path compression: after find(x), make every node on the path from $x$ point directly to the root. This is correct because it only moves pointers within one tree: every node still reaches the same root, so no set changes.

Lemma (union by rank alone). A root of rank $k$ has at least $2^k$ nodes in its tree.

Proof.

1. $k = 0$: a single node, and $2^0 = 1$.
2. A root's rank grows to $k + 1$ only when two roots of rank $k$ are joined. By induction each tree has at least $2^k$ nodes, so the new tree has at least $2^{k+1}$.
3. A tree never loses nodes, so the bound stays true. Hence the rank, and the height, are at most $\log_2 n$, and find costs $O(\log n)$. $\blacksquare$

With both rules, $m$ operations cost $O(m\,\alpha(n))$, where $\alpha$ is the inverse Ackermann function (Tarjan, 1975; we state this without proof). $\alpha(n) \le 4$ for any $n$ you will ever store, so in an interview say "almost constant time per operation, amortized".

Interactive figure: loading…

When to use it. Connectivity when edges arrive one by one ("are $x$ and $y$ connected now?"); cycle detection in an undirected graph (an edge whose two ends already have the same root closes a cycle: "Redundant Connection"); grouping equal things ("Accounts Merge"); and Kruskal's algorithm for a minimum spanning tree (sort the edges by weight, keep an edge when its two ends are in different sets). Union-find cannot delete edges.

Dijkstra's algorithm #

Dijkstra solves single-source shortest paths when every weight is $\ge 0$. Keep dist ($\infty$ everywhere, except $\text{dist}[s] = 0$) and a min-heap of pairs $(\text{dist}, \text{node})$. Take out the smallest pair. If it is stale (its distance is larger than the current $\text{dist}[u]$), skip it. Otherwise relax every edge $u \to v$: if $\text{dist}[u] + w(u, v) < \text{dist}[v]$, set $\text{dist}[v]$ to the smaller value and push the new pair. Python's heapq has no "decrease-key" operation, so you push a duplicate and skip the old pair later: this is called lazy deletion. Let $\delta(v)$ be the true weighted distance.

Theorem 6 (Dijkstra). If all weights are $\ge 0$, then when a node $u$ is taken out of the heap (and the pair is not stale), $\text{dist}[u] = \delta(u)$.

Proof.

1. Suppose not. Let $u$ be the first node taken out with $\text{dist}[u] > \delta(u)$, and let $P$ be a shortest path from $s$ to $u$.
2. Let $y$ be the first node on $P$ that is not yet taken out, and $x$ the node just before it on $P$ ($s$ is taken out first, with distance 0, so $x$ exists). Since $x$ was taken out before $u$, $\text{dist}[x] = \delta(x)$, and its edge to $y$ was relaxed: $\text{dist}[y] \le \delta(x) + w(x, y) = \delta(y)$. The heap holds a pair for $y$ with this distance.
3. All weights are $\ge 0$, so the part of $P$ after $y$ has length $\ge 0$. Hence $\delta(y) \le \delta(u)$.
4. So $\text{dist}[y] \le \delta(y) \le \delta(u) < \text{dist}[u]$. But the heap chose $u$ while the pair of $y$ was inside, so $\text{dist}[u] \le \text{dist}[y]$: a contradiction. (If $y = u$, step 2 already gives $\text{dist}[u] \le \delta(u)$.) $\blacksquare$

Step 3 is exactly where a negative edge breaks the proof. Cost: at most $E$ pushes, each $O(\log E) = O(\log V)$ (because $E \le V^2$): $O((V + E) \log V)$ time and $O(V + E)$ memory.

Interactive figure: loading…

What to use for other weights:

Weights	Algorithm	Time
all equal	BFS	$O(V + E)$
0 or 1	0-1 BFS (deque)	$O(V + E)$
all $\ge 0$	Dijkstra with a binary heap	$O((V + E) \log V)$
any, on a DAG	relax the edges in topological order	$O(V + E)$
any, no negative cycle	Bellman-Ford: $V - 1$ rounds that relax every edge; if a $V$-th round still improves a distance, there is a negative cycle	$O(VE)$

Other path costs, and minimum spanning trees

Dijkstra works for other path costs if two conditions hold: extending a path never lowers its cost, and of two paths to the same node, the cheaper one stays at least as cheap after the same next edge. "The largest single step on the path" satisfies both ("Path With Minimum Effort": use $\max(d, w)$ instead of $d + w$). A cost that depends on the previous edge (a turn penalty) breaks the second condition; then the state must be (node, last edge), not the node.

A minimum spanning tree (MST) connects all nodes of a connected undirected graph with the smallest total weight. Cut property: for any split of the nodes into two groups, a lightest edge that crosses the split belongs to some MST. Kruskal (sort the edges, keep an edge when union-find joins two different sets) costs $O(E \log E)$. Prim grows one tree with a heap keyed by edge weight: the whatever-first loop with a priority queue keyed by the last edge.

Answers to section 1. (1) No. DFS finds some path, which can be long. On the cycle $a - b - c - d - a$, DFS from $a$ may reach $d$ through $b$ and $c$ (3 edges), although the edge $a - d$ is 1 step. In the second figure, DFS reaches $G$ after 6 edges and BFS after 3. BFS gives the fewest edges because it discovers nodes in order of distance (Theorem 4). (2) Dijkstra reports $B = 2$: $B$ leaves the heap with 2 and is final before $C$ is processed. The true distance is 1, through $A \to C \to B$. Step 3 of the proof fails: the rest of the path after $C$ has negative length. Use Bellman-Ford. (A lazy version that lets a final node be improved again would fix this small case, but then "taken out means final" is false, and on bad inputs the work can grow exponentially; see Erickson §8.6.)

4. Worked example #

(a) One tree, all the views.

        4
      /   \
     2     6
    / \     \
   1   3     7

1. Traversals. Pre-order: node, left, right gives 4 2 1 3 6 7. In-order: left, node, right gives 1 2 3 4 6 7. Post-order: left, right, node gives 1 3 2 7 6 4. Level order: [[4], [2, 6], [1, 3, 7]].
2. BST? The in-order sequence 1 2 3 4 6 7 strictly increases, so by Theorem 1 this is a BST.
3. Height and space. The height is $h = 2$ edges ("maximum depth" in LeetCode counts nodes: 3). A DFS keeps at most $h + 1 = 3$ nodes on its stack; level order keeps up to 3 nodes (the last level) in its queue.
4. Serialization. 4,2,1,#,#,3,#,#,6,#,7,#,#: $n = 6$ values and $7 = n + 1$ markers.
5. LCA in the BST. $(1, 3)$: at 4 both are smaller, go left; at 2 we have $1 < 2 < 3$, stop: LCA 2. $(3, 7)$: at 4, $3 < 4 < 7$, stop: LCA 4. $(6, 7)$: at 4 both are larger, go right; at 6 the node equals $p$, stop: LCA 6.
6. Diameter. At node 4, the left subtree has height 1 and the right subtree has height 1, so the path through 4 has $1 + 1 + 2 = 4$ edges: $1 - 2 - 4 - 6 - 7$. No other node gives more.

(b) Dijkstra on a small graph. Directed edges $A \to B$ (4), $A \to C$ (1), $C \to B$ (2), $B \to D$ (1), $C \to D$ (5), $D \to E$ (3). Start at $A$. Distances are listed in the order $A, B, C, D, E$.

Take out	Action	dist	Heap after
$(0, A)$	relax: $B = 4$, $C = 1$	$0, 4, 1, \infty, \infty$	$(1,C), (4,B)$
$(1, C)$	relax: $B = 3$ (improved), $D = 6$	$0, 3, 1, 6, \infty$	$(3,B), (4,B), (6,D)$
$(3, B)$	relax: $D = 4$ (improved)	$0, 3, 1, 4, \infty$	$(4,B), (4,D), (6,D)$
$(4, B)$	stale ($4 > 3$), skip	same	$(4,D), (6,D)$
$(4, D)$	relax: $E = 7$	$0, 3, 1, 4, 7$	$(6,D), (7,E)$
$(6, D)$	stale ($6 > 4$), skip	same	$(7,E)$
$(7, E)$	no outgoing edges	same	empty

The shortest-path tree is $A \to C \to B \to D \to E$. Look at $B$: it is first pushed with 4 (through $A$), then improved to 3 (through $C$). This is why Dijkstra must not treat a node as final when it is pushed. That wrong version keeps $B = 4$, $D = 6$ and $E = 9$.

(c) Kahn on a pipeline. Tasks: download → preprocess; preprocess → train; preprocess → stats; train → evaluate; evaluate → report; stats → report. In-degrees: download 0, preprocess 1, train 1, stats 1, evaluate 1, report 2. The queue starts with download. Output download: preprocess drops to 0. Output preprocess: train and stats drop to 0. Output train: evaluate drops to 0. Output stats: report drops to 1. Output evaluate: report drops to 0. Output report. All 6 tasks are output, so there is no cycle. By levels: {download}, {preprocess}, {train, stats}, {evaluate}, {report}, that is 5 rounds, the number of nodes on the longest path.

5. In code #

Python's standard library plus SciPy for the check. The code reproduces the worked examples.

from collections import deque
import heapq
import math
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra as scipy_dijkstra


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


root = Node(4, Node(2, Node(1), Node(3)), Node(6, None, Node(7)))   # the tree of (a)


def inorder_iterative(root):
    """In-order with an explicit stack: O(n) time, O(h) extra space."""
    out, stack, node = [], [], root
    while stack or node:
        while node:                       # go left as far as possible
            stack.append(node)
            node = node.left
        node = stack.pop()                # the smallest value not visited yet
        out.append(node.val)
        node = node.right                 # its right subtree comes next
    return out


def is_bst(node, low=-math.inf, high=math.inf):
    """Every value must lie in the open interval (low, high) passed down from above."""
    if node is None:
        return True
    if not (low < node.val < high):
        return False
    return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)


def serialize(node):
    """Pre-order with a marker # for every missing child."""
    if node is None:
        return ["#"]
    return [str(node.val)] + serialize(node.left) + serialize(node.right)


def lca_bst(root, p, q):
    """Walk down while p and q are on the same side. O(h) time, O(1) space."""
    node = root
    while True:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node.val


print(inorder_iterative(root), is_bst(root))           # [1, 2, 3, 4, 6, 7] True
print(",".join(serialize(root)))                       # 4,2,1,#,#,3,#,#,6,#,7,#,#
print(lca_bst(root, 1, 3), lca_bst(root, 3, 7), lca_bst(root, 6, 7))   # 2 4 6
bad = Node(5, Node(3, None, Node(6)), Node(8))          # 6 is in the left subtree of 5
print(inorder_iterative(bad), is_bst(bad))             # [3, 6, 5, 8] False


def kahn(n, edges):
    """Topological order of nodes 0..n-1, or [] if there is a cycle. O(V + E)."""
    succ, indeg = [[] for _ in range(n)], [0] * n
    for u, v in edges:
        succ[u].append(v)
        indeg[v] += 1
    queue = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in succ[u]:
            indeg[v] -= 1
            if indeg[v] == 0:             # the last prerequisite of v is done
                queue.append(v)
    return order if len(order) == n else []


# 0 download, 1 preprocess, 2 train, 3 stats, 4 evaluate, 5 report
pipeline = [(0, 1), (1, 2), (1, 3), (2, 4), (4, 5), (3, 5)]
print(kahn(6, pipeline))                               # [0, 1, 2, 3, 4, 5]
print(kahn(6, pipeline + [(5, 1)]))                    # [] (report -> preprocess closes a cycle)


def dijkstra(n, edges, s):
    """Dijkstra with a binary heap and lazy deletion. Weights must be >= 0."""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [math.inf] * n
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # stale entry: u was improved after this push
        for v, w in adj[u]:
            if d + w < dist[v]:           # relax the edge u -> v
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist


edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]   # (b), A..E = 0..4
print(dijkstra(5, edges, 0))                           # [0, 3, 1, 4, 7]
u, v, w = zip(*edges)
print(scipy_dijkstra(csr_matrix((w, (u, v)), shape=(5, 5)), directed=True, indices=0))
# [0. 3. 1. 4. 7.]

is_bst and serialize are recursive, which is fine for interview-size trees; for trees deeper than about 1,000 levels, use an explicit stack as in inorder_iterative.

6. Where it shows up #

• Autograd and schedulers. The backward pass must finish a node's gradient before it passes it on: a reverse topological order of the computation graph. PyTorch's autograd engine counts the dependencies of each node and runs a node when its count reaches 0, which is Kahn's in-degree idea. Workflow tools (Airflow, Slurm job dependencies, build systems) run DAGs of tasks in the same way.
• Graph neural networks and ML for science. Message passing on molecules, meshes and particle systems (MeshGraphNets for PDE simulation, GraphCast for weather on a multi-mesh). $k$ layers of message passing see the $k$-hop neighbourhood of a node: the BFS ball of radius $k$.
• Trees in ML. A decision tree predicts with one root-to-leaf walk; gradient-boosted trees sum many such walks. k-d trees and ball trees (sklearn.neighbors.KDTree, BallTree) answer nearest-neighbour queries; Barnes-Hut octrees compute $n$-body forces in $O(n \log n)$.
• Tries in language models. Tokenizers store their vocabulary in a trie for longest-match lookups, and constrained decoding (for example, generating only valid entity names) walks a prefix tree of the allowed outputs.
• Clustering and manifolds. Connected components of a k-nearest-neighbour graph give clusters; single-linkage clustering is Kruskal's algorithm stopped early. Isomap approximates geodesic distances by shortest paths (Dijkstra) on a k-NN graph.

7. Common mistakes #

• BFS marks a node when it is taken out, not when it is put in. The same node then enters the queue many times. Also: forgetting to mark the start node.
• Checking a BST only against the parent. Pass the interval $(low, high)$ down; use math.inf for the open ends.
• Recursion on deep trees or big grids gives RecursionError in Python. Use an explicit stack.
• BFS with list.pop(0), which costs $O(n)$ per pop. Use collections.deque.
• An undirected graph stored in one direction only. Add both $u \to v$ and $v \to u$.
• Two colours for directed cycle detection. A diamond then looks like a cycle; use three colours, or Kahn's count.
• Dijkstra that finalizes a node when it is pushed (wrong distances, worked example (b)), that does not skip stale entries (wasted work), or that runs on negative weights.
• Union-find without either rule: a chain of unions makes one find cost $O(n)$.
• Grids: mixing (row, col) with (x, y), missing bounds checks, or changing the caller's grid.

8. Check yourself #

1. Give the level order and the in-order of the tree with root 8, children 3 and 10, where 3 has children 1 and 6, and 10 has a right child 14. Is it a BST?
   Answer

   Level order [[8], [3, 10], [1, 6, 14]]. In-order 1 3 6 8 10 14. It strictly increases, so the tree is a BST (Theorem 1).
2. How many # markers does the pre-order serialization of a 10-node tree contain? Why?
   Answer

   11. The 10 nodes have 20 child places; 9 are filled (every node except the root is a child once), so 11 are empty.
3. A grid has 3 rows and 4 columns, with moves up, down, left and right and no walls. How many nodes and undirected edges does its graph have?
   Answer

   12 nodes. Edges: $3 \cdot 3 = 9$ horizontal plus $2 \cdot 4 = 8$ vertical, so 17. In general $R(C-1) + C(R-1)$, and BFS costs $O(RC)$.
4. How many topological orders does the DAG $a \to b$, $a \to c$, $b \to d$, $c \to d$ have?
   Answer

   Two: $a, b, c, d$ and $a, c, b, d$. Kahn's queue holds both $b$ and $c$ at the same time; either can go first.
5. Union-find on $0, 1, 2, 3$ with union by rank (on a tie, the root of $b$ goes under the root of $a$). Run union(0,1), union(2,3), union(0,2). Give parent and rank, then parent after find(3) with path compression.
   Answer

   union(0,1): tie, 1 under 0, rank of 0 becomes 1. union(2,3): 3 under 2, rank of 2 becomes 1. union(0,2): tie at rank 1, 2 under 0, rank of 0 becomes 2. So parent = [0, 0, 0, 2], rank = [2, 0, 1, 0]. find(3) follows 3 → 2 → 0 and compresses: parent = [0, 0, 0, 0].
6. All weights are 0 or 1. Which algorithm do you use, and what does it cost?
   Answer

   0-1 BFS with a deque (0-edges to the front, 1-edges to the back): $O(V + E)$. Dijkstra is also correct, but costs $O((V + E) \log V)$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Extra space of a depth-first traversal and of level order on a binary tree?

   Show answer

2. How do you validate a binary search tree?

   Show answer

3. How do you find the lowest common ancestor of $p \le q$ in a BST?

   Show answer

4. Why does a pre-order serialization need null markers?

   Show answer

5. In whatever-first search, what decides the algorithm?

   Show answer

6. When does BFS give shortest paths, and when must it mark a node?

   Show answer

7. How does Kahn's algorithm detect a cycle?

   Show answer

8. What are the two optimizations of union-find, and what do they give together?

   Show answer

9. What does Dijkstra need, and what does it cost with a binary heap?

   Show answer

10. Shortest paths with negative edge weights: which algorithm?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

Recognize the pattern from the wording:

The problem says	Try
depth, balanced, diameter, path sum	post-order function that returns a value; a global best for turning paths
per level, right side view, zigzag, minimum depth	BFS with a deque, one level per round
BST: validate, $k$-th smallest, range	sorted in-order, or pass $(low, high)$ down
lowest common ancestor	BST: walk down by value, $O(h)$; general tree: post-order, $O(n)$
serialize, rebuild from traversals	pre-order with null markers; pre-order plus in-order
prefix, autocomplete, dictionary with wildcards	trie (DFS on the trie for wildcards)
fewest steps, moves or transformations; all steps cost the same	BFS (multi-source if there are many starts)
count the groups, islands, provinces; is everything reachable	DFS or BFS from every unvisited node, or union-find
prerequisites, build order, dependencies, is there a cycle	topological sort (Kahn)
edges arrive over time; which edge is redundant	union-find
cheapest path, weights $\ge 0$	Dijkstra; negative weights or "at most $k$ edges" → Bellman-Ford rounds
connect everything at minimum cost	minimum spanning tree (Kruskal or Prim)

The routine to say aloud. (1) Ask: directed or undirected? Weighted? Can it be disconnected? How large are $V$ and $E$ (or $R$ and $C$)? (2) Say what a node and an edge are. (3) Name the template and its cost. (4) For a tree: say what your function returns for one subtree, and the space $O(h)$. (5) Test aloud on an empty input, one node, and a path or a cycle.

Typical questions and short model answers.

• "BFS or DFS: when do you use which?" — BFS when I need the fewest steps in an unweighted graph, or anything per level; it uses $O(w)$ memory, the width of the frontier. DFS when I only need reachability, components, cycle detection or a topological order; it uses $O(h)$ memory for the current path, and it is shorter to write. Both are $O(V + E)$. In Python I write DFS with an explicit stack, because the recursion limit is about 1,000.
• "Why does Dijkstra fail with negative weights?" — The proof says: when a node leaves the heap, any other path to it must pass through a node still in the heap, whose distance is already at least as large; the rest of that path only adds weight. A negative edge breaks the last step. For example, $A \to B$ (2), $A \to C$ (3), $C \to B$ ($-2$): $B$ is finalized at 2, but the true distance is 1. With negative weights I use Bellman-Ford, $O(VE)$, or relaxation in topological order on a DAG.
• "How do you detect a cycle in a directed graph? In an undirected graph?" — Directed: Kahn's algorithm outputs fewer than $V$ nodes, or DFS finds an edge to a grey node (three colours). Undirected: union-find (an edge whose ends already share a root), or DFS that meets a visited node that is not the parent.
• "Explain union-find and its cost." — A forest of parent pointers; find walks to the root, union links two roots. Union by rank keeps the height at most $\log_2 n$, because a root of rank $k$ has at least $2^k$ nodes. Path compression points the walked nodes at the root. Together: $O(\alpha(n))$ amortized, almost constant.
• "Validate a BST." — Pass an open interval down; the local parent check is wrong (I give the tree 5, 3, 8 with 6 under 3). Equivalent: the in-order sequence must strictly increase. $O(n)$ time, $O(h)$ space.

Typical follow-ups. "Return the path itself": keep a parent array and walk back from the target. "Without recursion": an explicit stack. "Many LCA queries": binary lifting, $O(n \log n)$ preparation and $O(\log n)$ per query. "The graph does not fit in memory": BFS frontier by frontier, or bidirectional search. "Edges are deleted": union-find cannot do this; recompute, or process the operations in reverse order as additions.

10. Practice #

The notebook for this lesson runs in Colab. Each exercise has a check cell that compares your code with a library or a brute force on random inputs, and a folded solution:

1. level_order(root): the values level by level, with a deque.
2. is_valid_bst(root): the interval method, on random trees (some BSTs, some broken ones).
3. num_islands(grid): BFS or DFS on a grid; checked against scipy.ndimage.label.
4. course_order(n, prerequisites): Kahn's algorithm, [] on a cycle; checked with graphlib.TopologicalSorter.
5. dijkstra(n, edges, s): with heapq and lazy deletion; checked against scipy.sparse.csgraph.dijkstra.

Timed practice (25 minutes each, talking aloud): Binary Tree Level Order Traversal, Validate Binary Search Tree, Lowest Common Ancestor of a Binary Tree, Serialize and Deserialize Binary Tree, Number of Islands, Rotting Oranges, Course Schedule II, Redundant Connection, Network Delay Time.

Say it aloud (2 minutes, no notes): prove that BFS finds shortest paths in an unweighted graph, then explain which step of the Dijkstra proof needs non-negative weights.

11. Watch and read #

9. Breadth-First SearchMIT OpenCourseWare · 6.006 Introduction to Algorithms, Spring 2020 · 53 min

Graph representations, BFS level by level, and the shortest-path argument of section 3.

10. Depth-First SearchMIT OpenCourseWare · 6.006 Introduction to Algorithms, Spring 2020 · 52 min

DFS, connected components, topological sort by finishing times and cycle detection.

13. DijkstraMIT OpenCourseWare · 6.006 Introduction to Algorithms, Spring 2020 · 57 min

Relaxation, the invariant of Dijkstra, and why the weights must be non-negative.

Union Find IntroductionWilliamFiset · 6 min

The forest of parent pointers and what find and union do, before the optimizations.

Topological Sort | Kahn's Algorithm | Graph TheoryWilliamFiset · 14 min

Kahn's algorithm step by step with in-degrees, and how it detects a cycle.

• Jeff Erickson, Algorithms, free PDF: ch. 5 (graphs, whatever-first search), ch. 6 (depth-first search, topological sort), ch. 7 (minimum spanning trees), ch. 8 (shortest paths: BFS, Dijkstra also with negative edges §8.6, Bellman-Ford).
• MIT 6.006 Spring 2020, lecture notes and recitations (the course of the videos above).
• cp-algorithms, Disjoint Set Union: union by rank or size, path compression, and the complexity results.
• Sedgewick and Wayne, Algorithms, §3.2 Binary Search Trees: the cost of search in terms of the height, and the in-order traversal.
• Problem lists: Grind 75 (topics Binary Tree, Binary Search Tree, Graph) and NeetCode 150 (sections Trees, Tries, Graphs, Advanced Graphs).