L14–L19 Trees and Graphs

The creator’s written “25 patterns” list also names Union Find as pattern 19. In this playlist, L19 is topological sort.

L14. Trees and Traversals

Definition: a connected acyclic graph with one root. Each node has children; a binary tree allows at most two. A BST keeps left < node < right. Walks: inorder (left, node, right), preorder (node, left, right), postorder (left, right, node).

Real-world use:

Use this tree for the walk-throughs:

    1
   / \
  2   3

1. Inorder — left, node, right

BST values come out sorted. Result: [2,1,3].

Real-world use: print employees by salary, or files in a BST index in sorted order.

func InorderTraversal(root *TreeNode) []int {
	var out []int
	var walk func(*TreeNode)
	walk = func(n *TreeNode) {
		if n == nil {
			return
		}
		walk(n.Left)
		out = append(out, n.Val)
		walk(n.Right)
	}
	walk(root)
	return out
}

Complexity: time O(n), extra space O(h) recursion plus O(n) for the output. h is tree height.

2. Preorder — node, left, right

Useful to clone or serialize. Result: [1,2,3].

Real-world use: copy a menu tree or write a folder before writing its children.

func PreorderTraversal(root *TreeNode) []int {
	var out []int
	var walk func(*TreeNode)
	walk = func(n *TreeNode) {
		if n == nil {
			return
		}
		out = append(out, n.Val)
		walk(n.Left)
		walk(n.Right)
	}
	walk(root)
	return out
}

Complexity: time O(n), extra space O(h) recursion plus O(n) for the output.

3. Postorder — left, right, node

Children finish first. Result: [2,3,1].

Real-world use: delete a folder only after its files are gone, or compute a total from the leaves up.

func PostorderTraversal(root *TreeNode) []int {
	var out []int
	var walk func(*TreeNode)
	walk = func(n *TreeNode) {
		if n == nil {
			return
		}
		walk(n.Left)
		walk(n.Right)
		out = append(out, n.Val)
	}
	walk(root)
	return out
}

Complexity: time O(n), extra space O(h) recursion plus O(n) for the output.

4. Maximum depth

Empty tree is 0. Otherwise 1 + max(left, right).

Real-world use: how many manager layers sit above the deepest leaf employee, or the tallest HTML DOM.

    3
   / \
  9  20
    /  \
   15   7

Depth is 3.

func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left, right := MaxDepth(root.Left), MaxDepth(root.Right)
	if left > right {
		return left + 1
	}
	return right + 1
}

Complexity: time O(n), extra space O(h) recursion.

5. Same tree

Same shape and same values.

Real-world use: compare two org charts or two parsed expression trees for equality.

func IsSameTree(p, q *TreeNode) bool {
	if p == nil || q == nil {
		return p == q
	}
	return p.Val == q.Val &&
		IsSameTree(p.Left, q.Left) &&
		IsSameTree(p.Right, q.Right)
}

Complexity: time O(n), extra space O(h) recursion.

L15. DFS on Trees

Definition: go as deep as one branch allows, then backtrack. Recurse on children, then decide at the parent. On a tree you often do not need a visited set.

Real-world use:

1. Invert binary tree

Swap every left/right pair.

Real-world use: mirror a warehouse layout or flip a UI tree from LTR to RTL.

    4               4
   / \             / \
  2   7    →      7   2
 / \ / \         / \ / \
1  3 6  9       9  6 3  1
func InvertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = InvertTree(root.Right), InvertTree(root.Left)
	return root
}

Complexity: time O(n), extra space O(h) recursion.

2. Sum of left leaves

A left leaf is a left child with no children. Tree 3 / 9 20 / 15 7 → 9 + 15 = 24.

Real-world use: sum only the left-side leaf rooms of a building, or left-child SKUs in a catalog tree.

func SumOfLeftLeaves(root *TreeNode) int {
	if root == nil {
		return 0
	}
	sum := 0
	if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
		sum += root.Left.Val
	}
	return sum + SumOfLeftLeaves(root.Left) + SumOfLeftLeaves(root.Right)
}

Complexity: time O(n), extra space O(h) recursion.

3. Path sum

Root-to-leaf only. Subtract the node value and ask either child.

Real-world use: does any root-to-leaf budget path spend exactly target? Same idea as a bill that must match a receipt.

func HasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	if root.Left == nil && root.Right == nil {
		return root.Val == targetSum
	}
	remain := targetSum - root.Val
	return HasPathSum(root.Left, remain) || HasPathSum(root.Right, remain)
}

Complexity: time O(n), extra space O(h) recursion.

4. Balanced binary tree

Every node’s two subtree heights differ by at most 1. Return height, or -1 the moment a subtree is unbalanced, so the scan stays O(n).

Real-world use: is one team’s reporting line much deeper than the other? A balanced tree stays fast to search.

func IsBalanced(root *TreeNode) bool {
	var height func(*TreeNode) int
	height = func(n *TreeNode) int {
		if n == nil {
			return 0
		}
		left := height(n.Left)
		if left < 0 {
			return -1
		}
		right := height(n.Right)
		if right < 0 || left-right > 1 || right-left > 1 {
			return -1
		}
		if left > right {
			return left + 1
		}
		return right + 1
	}
	return height(root) >= 0
}

Complexity: time O(n), extra space O(h) recursion.

L16. BFS on Trees

Definition: visit a tree or graph level by level with a queue. Process exactly the nodes that are already in the queue before you add their children. The first time you reach a leaf is the shortest depth.

Real-world use:

1. Level order

Same as L10. Tree 3 / 9 20 / 15 7 → [[3],[9,20],[15,7]].

Real-world use: list everyone on each floor of an org chart before you go downstairs.

Complexity: time O(n), extra space O(w) for the queue plus O(n) for the output.

2. Zigzag level order

Same levels, reverse the odd ones → [[3],[20,9],[15,7]].

Real-world use: print a seating chart left-to-right, then the next row right-to-left.

func ZigzagLevelOrder(root *TreeNode) [][]int {
	levels := LevelOrder(root)
	for i, level := range levels {
		if i%2 == 1 {
			for l, r := 0, len(level)-1; l < r; l, r = l+1, r-1 {
				level[l], level[r] = level[r], level[l]
			}
		}
	}
	return levels
}

Complexity: time O(n), extra space O(w) for the queue plus O(n) for the output.

3. Minimum depth

First leaf the BFS reaches. Not the same as maximum depth on a skewed tree.

Real-world use: fewest hops from the CEO to the first individual contributor, or the nearest exit in a building tree.

func MinDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	queue := []*TreeNode{root}
	for depth, head := 1, 0; head < len(queue); depth++ {
		size := len(queue) - head
		for i := 0; i < size; i++ {
			n := queue[head]
			head++
			if n.Left == nil && n.Right == nil {
				return depth
			}
			if n.Left != nil {
				queue = append(queue, n.Left)
			}
			if n.Right != nil {
				queue = append(queue, n.Right)
			}
		}
	}
	return 0
}

Complexity: time O(n), extra space O(w) for the queue.

4. Maximum level sum

Sum each level. Return the 1-based level with the largest sum. Ties keep the smaller level index.

Real-world use: which storey of a building has the largest total salary, or which depth of a catalog sells the most.

func MaxLevelSum(root *TreeNode) int { /* see solutions.go */ }

Complexity: time O(n), extra space O(w) for the queue.

L17. Graphs

Definition: a set of nodes plus edges. Directed or undirected, weighted or not. Store edges as an n × n matrix (dense) or as an adjacency list (sparse). A grid is a graph whose neighbors are the four adjacent cells.

Real-world use:

1. Adjacency matrix

n x n. m[u][v] = weight (or 1). O(1) edge test, O(n²) space. Good for dense graphs.

Real-world use: “is there a direct flight from A to B?” when almost every city pair has a route.

func AdjMatrix(n int, edges [][]int, undirected bool) [][]int {
	m := make([][]int, n)
	for i := range m {
		m[i] = make([]int, n)
	}
	for _, e := range edges {
		u, v, w := e[0], e[1], 1
		if len(e) > 2 {
			w = e[2]
		}
		m[u][v] = w
		if undirected {
			m[v][u] = w
		}
	}
	return m
}

Complexity: build time O(n² + m), extra space O(n²). Edge test is O(1).

2. Adjacency list

g[u] is the neighbor list. O(n+m) space. Good for sparse graphs and walking neighbors.

Real-world use: a road map where each city has only a few roads; walk neighbors without scanning an n×n grid.

func AdjList(n int, edges [][]int, undirected bool) [][][2]int {
	g := make([][][2]int, n)
	for _, e := range edges {
		u, v, w := e[0], e[1], 1
		if len(e) > 2 {
			w = e[2]
		}
		g[u] = append(g[u], [2]int{v, w})
		if undirected {
			g[v] = append(g[v], [2]int{u, w})
		}
	}
	return g
}

Complexity: build time O(n + m), extra space O(n + m). Walking neighbors of u is O(degree(u)).

3. Flood fill

4-connected DFS/BFS. Recolor every cell equal to the start color. If the new color equals the start color, do nothing.

Real-world use: the paint-bucket tool in a drawing app, or fill a connected region on a map.

1 1 1      2 2 2
1 1 0  →   2 2 0
1 0 1      2 0 1

Start (1,1), color 2.

func FloodFill(image [][]int, sr, sc, color int) [][]int {
	start := image[sr][sc]
	if start == color {
		return image
	}
	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r < 0 || c < 0 || r >= len(image) || c >= len(image[0]) || image[r][c] != start {
			return
		}
		image[r][c] = color
		dfs(r+1, c)
		dfs(r-1, c)
		dfs(r, c+1)
		dfs(r, c-1)
	}
	dfs(sr, sc)
	return image
}

Complexity: time O(rows × cols), extra space O(rows × cols) in the worst DFS stack.

4. Rotting oranges

0 empty, 1 fresh, 2 rotten. Multi-source BFS: enqueue every rotten orange first. Each BFS layer is one minute. Return -1 if a fresh orange remains.

Real-world use: infection or warehouse spoilage spreading minute by minute from every already-rotten cell.

2 1 1
1 1 0   →  4 minutes
0 1 1
func OrangesRotting(grid [][]int) int { /* see solutions.go */ }

Complexity: time O(rows × cols), extra space O(rows × cols) for the queue.

L18. Dijkstra

Definition: shortest path from one source on a graph whose edge weights are non-negative. Grow a frontier with a min-heap of (node, distance). The first time you pop a node, that distance is final.

Real-world use:

Idea:

  1. dist[src] = 0, others +inf.
  2. Min-heap of (node, dist).
  3. Pop the closest unfinished node. Skip stale heap entries.
  4. Relax each outgoing edge: if dist[u]+w < dist[v], update and push.

This implementation treats edges as directed. Duplicate an edge both ways for an undirected graph. Negative weights need Bellman-Ford.

func Dijkstra(n int, edges [][]int, src int) []int {
	adj := make([][][2]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], [2]int{e[1], e[2]})
	}
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[src] = 0
	h := &dijkHeap{{node: src, dist: 0}}
	for h.Len() > 0 {
		cur := heap.Pop(h).(dijkItem)
		if cur.dist != dist[cur.node] {
			continue
		}
		for _, edge := range adj[cur.node] {
			if cand := cur.dist + edge[1]; cand < dist[edge[0]] {
				dist[edge[0]] = cand
				heap.Push(h, dijkItem{node: edge[0], dist: cand})
			}
		}
	}
	for i, d := range dist {
		if d == math.MaxInt {
			dist[i] = -1
		}
	}
	return dist
}

Complexity: time O((n + m) log n) with a binary heap, extra space O(n + m).

L19. Topological Sort

Definition: an ordering of a directed acyclic graph so every edge u → v has u before v. A cycle means no valid order. DFS pushes a node after its dependents; Kahn starts from indegree 0.

Real-world use:

1. DFS + stack

Visit neighbors first, then push u. Reverse the stack at the end. A back edge to a gray node is a cycle.

Real-world use: finish every dependency of a package, then emit the package — unless two packages depend on each other.

func TopoSortDFS(n int, edges [][]int) []int {
	const white, gray, black = 0, 1, 2
	adj := make([][]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
	}
	state := make([]int, n)
	out := []int{}
	cycle := false
	var dfs func(int)
	dfs = func(u int) {
		state[u] = gray
		for _, v := range adj[u] {
			if state[v] == gray {
				cycle = true
				return
			}
			if state[v] == white {
				dfs(v)
			}
		}
		state[u] = black
		out = append(out, u)
	}
	for i := 0; i < n; i++ {
		if state[i] == white {
			dfs(i)
		}
	}
	if cycle {
		return nil
	}
	for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
		out[i], out[j] = out[j], out[i]
	}
	return out
}

Complexity: time O(n + m), extra space O(n + m).

2. Kahn’s algorithm (BFS)

Start from indegree 0. Each processed node decrements its neighbors. If you cannot process all nodes, there is a cycle.

Real-world use: a build queue: jobs with no remaining prerequisites start first, like a factory line.

func TopoSortKahn(n int, edges [][]int) []int {
	indeg := make([]int, n)
	adj := make([][]int, n)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		indeg[e[1]]++
	}
	queue := []int{}
	for i, d := range indeg {
		if d == 0 {
			queue = append(queue, i)
		}
	}
	out := []int{}
	for head := 0; head < len(queue); head++ {
		u := queue[head]
		out = append(out, u)
		for _, v := range adj[u] {
			indeg[v]--
			if indeg[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	if len(out) != n {
		return nil
	}
	return out
}

Complexity: time O(n + m), extra space O(n + m).

3. Course schedule

prerequisites[i] = [course, pre] means pre → course. Possible iff a topo order exists.

Real-world use: can a student finish the degree, or is there a cycle such as “A needs B and B needs A”?

numCourses=2, [[1,0]] → true. [[1,0],[0,1]] → false.

func CanFinish(numCourses int, prerequisites [][]int) bool {
	edges := make([][]int, len(prerequisites))
	for i, p := range prerequisites {
		edges[i] = []int{p[1], p[0]}
	}
	return TopoSortKahn(numCourses, edges) != nil
}

Complexity: time O(n + m), extra space O(n + m).