Trees, graphs and the rest
By the end: You can handle tree and graph questions and the remaining common patterns.
- Tree traversal, both orders
- Graph traversal and topological sort
- Heaps and top-k
- Intervals, backtracking and one-dimensional dynamic programming
New to data structures & algorithms? Data structures are the standard ways of arranging data in memory, such as a list, a lookup table or a tree, and each makes some operations cheap and others expensive. Algorithms are the standard recipes for working through them. Big-O notation is the shorthand for how the cost grows as the data grows: a method that is fine on a hundred records can be unusable on a million, and this notation tells you which one you have before you find out in production. Why it matters
Tree and graph questions look harder than they are, because nearly all of them are the same two traversals with something extra attached. This section covers those and then clears the remaining ground: heaps for top-k, interval problems, backtracking, and the limited amount of dynamic programming that is actually asked. Together with the previous section that is the complete list worth drilling.
Trees#
Almost every tree question is a traversal with something extra. There are two, and knowing which you need is most of the work. Depth-first goes down one branch before trying the next, uses a stack or recursion, and is what you want for anything about paths, depth or structure. Breadth-first visits a whole level before descending, uses a queue, and is what you want for anything about levels or the shortest number of steps.
def depth(node):
"""Depth-first. The recursion is the stack."""
if node is None:
return 0
return 1 + max(depth(node.left), depth(node.right))
from collections import deque
def levels(root):
"""Breadth-first, one list per level. The len(queue) snapshot is the trick:
it fixes how many nodes belong to this level before any are added."""
if root is None:
return []
out, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)): # exactly this level
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
out.append(level)
return outA binary search tree adds one property: everything left of a node is smaller, everything right is larger. That makes lookup logarithmic, and it makes an in-order traversal produce the values in sorted order, which is the basis of most BST questions.
def inorder(node, out=None):
"""Left, self, right. On a BST this emits the values in sorted order."""
out = [] if out is None else out
if node:
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
return out
def is_bst(node, low=float("-inf"), high=float("inf")):
"""Every node must fit a range, not merely beat its parent."""
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))Comparing a node with its parent is not enough
A tree with root 10, left child 5, and that child's right child 12 satisfies every parent comparison and is not a search tree, because 12 sits in the left subtree of 10. The range has to be carried down. This is the most common wrong answer to the most common tree question.
Graphs#
A graph is the same two traversals with one addition: you must remember where you have been, or a cycle makes the search run forever. Almost every grid question is a graph question where the neighbours are the four adjacent cells. Breadth-first gives the shortest path when every edge costs the same, which is why it is the answer to most maze and spreading questions.
from collections import deque
def shortest_path(grid, start, goal):
"""Fewest steps through a grid of open cells. BFS, because every step
costs the same. Dijkstra is for when they do not."""
rows, cols = len(grid), len(grid[0])
queue = deque([(start, 0)])
seen = {start} # mark on push, not on pop
while queue:
(r, c), dist = queue.popleft()
if (r, c) == goal:
return dist
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and grid[nr][nc] != "#" and (nr, nc) not in seen):
seen.add((nr, nc))
queue.append(((nr, nc), dist + 1))
return -1Topological sort is the other graph algorithm worth having ready. It orders tasks so every dependency comes first, and it answers the build-order and course-schedule family. The version to remember counts incoming edges and repeatedly takes whatever has none left; if the output is shorter than the input, there was a cycle.
def topo_sort(nodes, edges):
"""edges are (before, after) pairs. Returns [] if there is a cycle."""
incoming = {n: 0 for n in nodes}
out = {n: [] for n in nodes}
for before, after in edges:
out[before].append(after)
incoming[after] += 1
ready = deque(n for n in nodes if incoming[n] == 0)
order = []
while ready:
n = ready.popleft()
order.append(n)
for nxt in out[n]:
incoming[nxt] -= 1
if incoming[nxt] == 0:
ready.append(nxt)
return order if len(order) == len(nodes) else []
topo_sort("abcd", [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")])
# ['a', 'b', 'c', 'd']Heaps and top-k#
A heap keeps the smallest item reachable in constant time and costs logarithmic time to push or pop. That is exactly what top-k needs: hold a heap of size k, and whenever something bigger arrives, drop the smallest. Sorting the whole input is n log n; this is n log k, which matters when n is large and k is ten.
import heapq
def top_k(nums, k):
"""Python's heapq is a min-heap, which is what you want here: the
smallest of the current best k sits at the top, ready to be evicted."""
heap = []
for n in nums:
if len(heap) < k:
heapq.heappush(heap, n)
elif n > heap[0]:
heapq.heapreplace(heap, n) # push and pop in one operation
return sorted(heap, reverse=True)
top_k([5, 1, 9, 3, 7, 8], 3) # [9, 8, 7]
# heapq.nlargest(k, nums) does the same thing and is the right answer in
# production. Interviewers usually want the loop.The variant worth rehearsing is the streaming one, because it is asked in near-identical form at several of the largest employers: find the top k items in a stream you cannot store. The answer is the same heap, kept at size k, with the stream passing through it — you hold k items rather than n, and each item costs a comparison against the smallest of them.
from collections import Counter
def top_k_stream(stream, k):
"""Exact top-k by frequency, holding k items rather than the stream."""
counts = Counter()
heap = [] # min-heap of (count, item), size <= k
in_heap = set()
for item in stream:
counts[item] += 1
if item in in_heap:
# Rebuild lazily: its count moved, so the heap order is stale.
heap = [(counts[i], i) for _, i in heap]
heapq.heapify(heap)
elif len(heap) < k:
heapq.heappush(heap, (counts[item], item))
in_heap.add(item)
elif counts[item] > heap[0][0]:
_, evicted = heapq.heapreplace(heap, (counts[item], item))
in_heap.discard(evicted)
in_heap.add(item)
return sorted(heap, reverse=True)The follow-up is always the same
Two of them. First: the counter still grows with the number of distinct items, so what do you do when that will not fit? The answer is that you give up exactness — Count-Min Sketch or Space-Saving give you approximate counts in fixed memory, and you say out loud which guarantee you are trading. Second: what breaks when it is sharded? Top-k is not decomposable. The global tenth-most-frequent item can be eleventh on every shard and appear in no shard's local top ten, so merging local top-k lists is wrong. You either merge full counts for candidate items or accept an approximation and say so.
Intervals#
Interval questions are almost all the same problem: sort by start, then walk through deciding whether the current interval touches the one you are building. Meeting rooms, merging ranges, and insert-and-merge are the same six lines with a different comparison. The sort is what makes it work, and forgetting it is the usual failure.
def merge(intervals):
"""Overlapping ranges collapsed into one. O(n log n), the sort dominates."""
if not intervals:
return []
intervals = sorted(intervals) # by start
merged = [list(intervals[0])]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # touches the one being built
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
merge([(1, 3), (2, 6), (8, 10), (15, 18)]) # [[1, 6], [8, 10], [15, 18]]The other shape counts overlaps rather than merging them — how many meeting rooms are needed at once. Treat every start as plus one and every end as minus one, sort the events, and the answer is the running maximum.
def max_rooms(meetings):
events = []
for start, end in meetings:
events.append((start, 1))
events.append((end, -1))
# An end at time t is processed before a start at time t: a room frees up
# exactly as the next meeting begins. -1 sorts before 1, which does it.
events.sort()
current = best = 0
for _, delta in events:
current += delta
best = max(best, current)
return best
max_rooms([(0, 30), (5, 10), (15, 20)]) # 2Backtracking#
Backtracking is exhaustive search with an undo. Choose, recurse, then put things back as they were so the next branch starts clean. Permutations, subsets, combinations, N-queens and sudoku are all the same skeleton, and writing that skeleton from memory is worth more than solving any one of them.
def permutations(items):
result, current, used = [], [], [False] * len(items)
def backtrack():
if len(current) == len(items):
result.append(current[:]) # copy, or every entry aliases
return
for i, item in enumerate(items):
if used[i]:
continue
used[i] = True # choose
current.append(item)
backtrack() # explore
current.pop() # undo
used[i] = False # undo
return
backtrack()
return result
permutations([1, 2, 3]) # [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]Appending the list instead of a copy
result.append(current) without the slice appends a reference to the same list, which is then mutated by the rest of the search. You end up with the right number of results and every one of them empty or identical. It is the single most common backtracking bug and it looks like a logic error rather than an aliasing one.
One-dimensional dynamic programming#
Far less of this is asked than the reputation suggests, and what is asked is almost always one-dimensional: an array where each entry is built from a few earlier ones. Work out what one entry means in words before writing any code, because that sentence is the whole solution and everything else follows from it.
def climb_stairs(n):
"""dp[i] = the number of distinct ways to reach step i.
You arrive from one step below or two, so the ways add."""
if n <= 2:
return n
a, b = 1, 2 # ways to reach steps 1 and 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
def coin_change(coins, amount):
"""dp[i] = fewest coins summing to exactly i, or infinity if impossible."""
dp = [0] + [float("inf")] * amount
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
return -1 if dp[amount] == float("inf") else dp[amount]
coin_change([1, 5, 6, 9], 11) # 2, using 5 + 6The recognition signal is a question asking for the number of ways, or the best value, where a choice at each step affects what remains. If you can state what one array entry means and how it is built from earlier ones, you have finished the hard part.
What to drill, and what to skip#
Worth drilling Rarely worth it
tree traversal, both kinds red-black and AVL rotations
BFS on a grid Dijkstra, unless the job is routing
topological sort minimum spanning trees
heap for top-k Fibonacci heaps
interval merge and room counting segment trees, Fenwick trees
backtracking skeleton bitmask dynamic programming
one-dimensional dynamic programming two-dimensional, except edit distanceWhere people go wrong
Appending a mutable list in backtracking without copying it. Every entry in the result then points at the same list, which ends up empty. It looks like the algorithm failed when the algorithm was fine.
If this comes up in an interview
When would you use BFS rather than DFS?
When the question involves levels, or the shortest path in an unweighted graph, since BFS reaches nodes in order of distance. DFS suits paths, subtree properties and anything naturally recursive.
How do you find the top k elements efficiently?
Keep a heap of size k rather than sorting everything. That is n log k rather than n log n, and it works on a stream where you cannot hold all the data at once.
What does topological sort solve?
Ordering with dependencies: course prerequisites, build order, task scheduling. It also detects cycles, since a cycle means some nodes never reach indegree zero and the output is shorter than the input.
What is the difference between recursion and backtracking?
Backtracking is recursion that undoes its choice before trying the next one. The undo step, usually a pop, is what makes it backtracking, and forgetting it is the most common bug in these problems.
Build this: Do 15 tree problems, 12 graph problems and 8 each of the rest. Time yourself: 25 minutes is the realistic interview budget for a medium question including explanation.
Watch it explained
This is one section of Data structures & algorithms, 40 hours across 4 sections. Read it in full to get the whole topic in order.
Stop 44 of 50 on the AI Engineer route
0 of 50 topics done · 0h behind you, 603h to go
What you have marked done is stored in this browser only. It does not reach a server, and clearing site data will clear it.