Level order
StopBinary tree
- CH4 queue
22/22
Breadth-first on a tree: drain one level's worth of the queue at a time.
Step through it →Graph Traversal (BFS & DFS)
Breadth-first and depth-first search reach everything connected to a start, and mark each node the moment they find it, so nothing is visited twice.
Number of islands: one flood fill per island
StopGrid
grid
- CH4 queue
islands = 0, and no cell has been seen. The scan reads the 4 × 4 grid row by row.
Typical cost O(V + E) time, O(V) spaceFull lesson: Number of Islands →
When to reach for it
- The input is a grid, a tree, or a list of what connects to what.
- You're asked what's reachable, how many groups there are, or how far apart two things are.
- Without marking, you'd reach the same cell or node from several sides.
- A copy or a count has to follow every edge once.
What stays true
A cell is marked as it's queued, and the check that queues a neighbor skips seen cells. So a cell reachable from two sides is queued by whichever gets there first, and never again.
Nothing is queued twice
StopGrid
InvariantEvery cell in the queue is already marked seen.✓ Holds
- CH4 queue
islands = 0, and no cell has been seen. The scan reads the 4 × 5 grid row by row.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Code that also checks the four diagonals joins these five cells into one island. Up, down, left and right keep them apart.
Number of islands on the grids that trip it up
StopGrid
- CH4 queue
islands = 0, and no cell has been seen. The scan reads the 3 × 3 grid row by row.
Answer5Steps31
Variants
Maximum depth
StopBinary tree
- CH1 node
- CH4 call stack
26/26
Depth-first on a tree: each node returns one more than its deeper subtree.
Step through it →Invert a binary tree
StopBinary tree
- CH1 node
- CH4 call stack
29/29
Visit every node once and swap its two children.
Step through it →Clone graph
StopGraph
- CH4 queue
20/20
Breadth-first with a map: make each node's clone the moment it's first seen.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Number of islands: one flood fill per island
StopGrid
- CH4 queue
islands = 0, and no cell has been seen. The scan reads the 4 × 4 grid row by row.
number_of_islands.py
from collections import dequedef num_islands(grid): rows, cols = len(grid), len(grid[0]) seen = set() islands = 0 for r in range(rows): for c in range(cols): if grid[r][c] != "1" or (r, c) in seen: continue islands += 1 seen.add((r, c)) queue = deque([(r, c)]) while queue: row, col = queue.popleft() for nr, nc in ((row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)): if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and (nr, nc) not in seen: seen.add((nr, nc)) queue.append((nr, nc)) return islands