Trees & Graphs

⏱️ ~3-minute bite · solve the sandbox to master

0%lesson

🧒

5-Year-Old Metaphor

— The physical, real-world picture. No jargon.

🌊 BFS = ripples in a pond. 🧶 DFS = exploring a maze with a thread.

BFS — ripples in a pond

Drop a stone in still water. The ripple expands outward in concentric rings — every point at distance 1 is wet before any point at distance 2. BFS works exactly the same way. It visits all neighbors of a node before moving to their neighbors. The "rings" are the levels of the graph.

This is why BFS finds the shortest path in an unweighted graph: the first time BFS reaches a destination node, it took the fewest hops. Any shorter path would have been found first.

DFS — maze explorer with a thread

Imagine exploring a maze holding one end of a thread. You walk forward until you hit a dead end, then follow the thread back to the last fork and try the next passage. DFS does exactly this — it commits fully to one branch before backtracking.

The "thread" in code is the call stack (or explicit stack). When you backtrack, you pop the stack. DFS is natural for problems that require exploring all possibilities: permutations, maze solving, detecting cycles.

Trees vs Graphs — what's the difference?

Tree

Acyclic (no loops)
Connected (one piece)
Exactly N-1 edges for N nodes
Exactly one path between any two nodes
No need for visited set during traversal

Graph

May have cycles
May be disconnected
Any number of edges
Multiple paths possible
Always use a visited set

A tree is just a graph with extra constraints. Every tree algorithm works on a graph, but not vice-versa.

🎛️

Interactive Sandbox

— Move something, see it react instantly.

How to use: select a traversal pattern, then step through it. Explore all 5 patterns to master this topic. Purple = current node, green = visited, gray = unvisited.

Nodes

Edges:A→BA→CB→DB→EC→F

Queue (front → back)

[1/7]Enqueue start node A. Queue = [A]

0/5 explored

⚠ Gotcha: Always check visited before enqueuing — without it you'll enqueue the same node multiple times in a graph with shared parents.

💡 Insight: BFS explores level by level. In an unweighted graph, the first time BFS reaches a node is via the shortest path.

🎯

Challenge

Explore all 5 traversal patterns by stepping to the end of each. Explored: 0/5 (none yet)

Try it

🎯

Why Should I Care?

— The exact interview question + the bug it kills.

Interview question 1

"When do you use BFS vs DFS? Give a concrete example for each."

Use BFS when:

Shortest path in unweighted graph
Level-order tree traversal
"Minimum steps/hops" problems
Word ladder, 0-1 matrix distance

Use DFS when:

Cycle detection
Topological sort
Path existence (any path, not shortest)
All permutations / combinations
Connected components in a grid

Interview question 2

"Why does BFS find the shortest path in an unweighted graph?"

Because BFS processes nodes in order of their distance from the source. The queue always contains nodes at distance d before nodes at distance d+1. The first time BFS reaches the target, it must have taken the minimum number of edges — any shorter route would have been explored first.

1	function shortestPath(graph: Map<string, string[]>, start: string, end: string): number {
2	const queue: [string, number][] = [[start, 0]];
3	const visited = new Set([start]);
4	while (queue.length) {
5	const [node, dist] = queue.shift()!;
6	if (node === end) return dist;
7	for (const neighbor of graph.get(node) ?? []) {
8	if (!visited.has(neighbor)) {
9	visited.add(neighbor);
10	queue.push([neighbor, dist + 1]);
11	}
12	}
13	}
14	return -1; // unreachable
15	}
16	// Time: O(V + E) · Space: O(V)

Interview question 3

"What is topological sort and when is it possible?"

Topological sort is a linear ordering of vertices such that for every directed edge u→v, vertex u comes before v. It is only possible on a DAG (Directed Acyclic Graph). If there's a cycle, no valid ordering exists — run cycle detection first. Used for: build systems, task scheduling with dependencies, course prerequisite order.

Classic bug

Forgetting the visited set → infinite loop on cyclic graphs

Broken (no visited set)

1	function bfs(graph, start) {
2	const queue = [start];
3	while (queue.length) {
4	const node = queue.shift();
5	console.log(node); // visits A→B→C→A→...
6	for (const n of graph[node])
7	queue.push(n); // 💥 infinite loop
8	}
9	}

Fixed (visited set)

1	function bfs(graph, start) {
2	const visited = new Set([start]);
3	const queue = [start];
4	while (queue.length) {
5	const node = queue.shift();
6	console.log(node);
7	for (const n of graph[node]) {
8	if (!visited.has(n)) {
9	visited.add(n); // ✅
10	queue.push(n);
11	}
12	}
13	}
14	}

🔬

The Deep Dive

— Spec refs, engine internals, the minutiae.

Space complexity — BFS vs DFS

BFS — O(w) queue width

The queue holds all nodes at the current frontier. In the worst case (a complete binary tree, last level), that's O(n/2) = O(n) nodes. For wide, shallow graphs BFS is memory-heavy.

Rule of thumb: if the tree is wide (large branching factor), BFS queue explodes.

DFS — O(h) stack height

The stack only holds the current path root-to-leaf. Max depth = O(h) where h is tree height. For balanced trees h = O(log n); for skewed trees h = O(n).

Rule of thumb: if the tree is deep and narrow, DFS is memory-efficient.

Dijkstra — BFS extended with weights

Dijkstra's algorithm is BFS with a min-heap (priority queue) instead of a plain queue. Instead of processing nodes FIFO, it always processes the node with the smallest accumulated distance first. This guarantees the shortest path even in weighted graphs — as long as weights are non-negative.

1	// Conceptually:
2	// BFS: queue → process by insertion order (unweighted shortest path)
3	// Dijkstra: min-heap → process by cumulative cost (weighted shortest path)
4	// A*: min-heap sorted by cost + heuristic (guided Dijkstra)

Graph representations

Adjacency List

1	// Map<node, neighbor[]>
2	const g = new Map([
3	["A", ["B","C"]],
4	["B", ["D","E"]],
5	["C", ["F"]],
6	]);

Space: O(V + E)
Traverse neighbors: O(degree)
Best for sparse graphs

Adjacency Matrix

1	// boolean[V][V]
2	// A B C
3	// A[0, 1, 1]
4	// B[0, 0, 0]
5	// C[0, 0, 0]

Space: O(V²)
Edge lookup: O(1)
Best for dense graphs

Connected components

A connected component is a maximal set of nodes where every node is reachable from every other node. To count components: iterate over all nodes, run BFS/DFS from any unvisited node, mark all nodes reached as one component. Repeat until all nodes are visited.

1	function countComponents(n: number, edges: [number,number][]): number {
2	const adj: number[][] = Array.from({length: n}, () => []);
3	for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
4	const visited = new Set<number>();
5	let count = 0;
6	for (let i = 0; i < n; i++) {
7	if (!visited.has(i)) {
8	dfs(i, adj, visited); // mark whole component
9	count++;
10	}
11	}
12	return count;
13	}
14	// Time: O(V + E)

Bipartite check

A graph is bipartite if its nodes can be split into two groups where every edge connects a node from group 1 to group 2. Equivalently: you can color the graph with 2 colors such that no two adjacent nodes share a color. Run BFS and alternate colors. If you encounter two same-colored neighbors, it's not bipartite. All trees are bipartite. Any odd-length cycle makes it non-bipartite.

Time complexity reference

Algorithm	Time	Space
BFS	O(V + E)	O(V) queue
DFS	O(V + E)	O(V) stack
In-order / Level-order	O(n)	O(h) / O(w)
Dijkstra (binary heap)	O((V+E) log V)	O(V)
Topological Sort (Kahn's)	O(V + E)	O(V)

🎤

Interview Questions

— Real questions from real interviews — with answers.

BFS explores level by level (shortest path); DFS explores depth-first (cycle detection, topological sort, path existence).

DFS with a 3-color scheme: white (unvisited), gray (in current path), black (fully processed) — a gray node encountered again means a cycle.

Trees are acyclic connected graphs with a root — graphs can have cycles, disconnected components, and no designated root.

Adjacency list for sparse graphs (O(V+E) space); adjacency matrix for dense graphs or when O(1) edge-existence lookup is critical.

Greedy shortest-path using a min-heap to always process the closest unvisited node — O((V+E) log V).

🎮

Memory Game

— Quick quiz — lock the concept in long-term memory.

1/4

In-order traversal of a BST produces what ordering?