Step 3 · DSA
Two ways to walk
🤔
Round 2 at a campus drive. Aarav gets "print the tree level by level". He knows what BFS is. He cannot remember whether it uses a queue or a stack, so he freezes for four minutes. He knew the idea. He had never typed the template.
Every traversal question is the same loop with one thing changed. BFS uses a queue and spreads out one ring at a time. DFS uses a stack (or recursion, which is a stack) and runs down one path to the end before coming back.
1 BFS (queue) -> 1 · 2 3 · 4 5 6
/ \ spreads level by level
2 3
/ \ \ DFS (stack) -> 1 2 4 5 3 6
4 5 6 runs to the end of one path first
The one law: mark a node as seen the moment you push it, never when you pop it. Push-time marking is what stops the same node entering the queue twice.
Every Python template below assumes from collections import deque. Every Java template assumes import java.util.*; and a tree node class with fields val, left, right.
Binary tree: BFS and DFS
Visited rule: a tree has no cycles, so you need no visited set at all. The only guard is the null check on a child.
Template 1 · Tree BFS · returns 1 2 3 4 5 6
Python
def bfs_tree(root):
if not root:
return []
order = []
q = deque([root])
while q:
node = q.popleft()
order.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return order
Java
List<Integer> bfsTree(Node root) {
List<Integer> order =
new ArrayList<>();
if (root == null) return order;
Queue<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
Node node = q.poll();
order.add(node.val);
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
}
return order;
}
Template 2 · Tree DFS (preorder) · returns 1 2 4 5 3 6
Python
def dfs_tree(node, order):
if not node:
return
order.append(node.val)
dfs_tree(node.left, order)
dfs_tree(node.right, order)
Java
void dfsTree(Node node,
List<Integer> order) {
if (node == null) return;
order.add(node.val);
dfsTree(node.left, order);
dfsTree(node.right, order);
}
DFS without recursion: take Template 1, pop from the end of the list instead of the front, and push the right child first. Same loop, depth-first order. In Java, use a Deque with push and pop.
Graph: BFS and DFS
g[u] is the list of neighbours of u (in Java, Map<Integer, List<Integer>>). Test graph: {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}.
Visited rule: a graph has cycles, so the visited set is not optional. Add to seen in the same two lines that push, or node 0 comes back around forever.
Template 3 · Graph BFS from 0 · returns 0 1 2 3 4
Python
def bfs_graph(g, start):
seen = {start}
order = []
q = deque([start])
while q:
u = q.popleft()
order.append(u)
for v in g[u]:
if v in seen:
continue
seen.add(v)
q.append(v)
return order
Java
List<Integer> bfsGraph(
Map<Integer, List<Integer>> g,
int start) {
List<Integer> order =
new ArrayList<>();
Set<Integer> seen = new HashSet<>();
Queue<Integer> q = new ArrayDeque<>();
seen.add(start);
q.add(start);
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : g.get(u)) {
if (seen.contains(v)) continue;
seen.add(v);
q.add(v);
}
}
return order;
}
Template 4 · Graph DFS from 0 · returns 0 1 3 2 4
Python · call with seen=set(), order=[]
def dfs_graph(g, u, seen, order):
seen.add(u)
order.append(u)
for v in g[u]:
if v not in seen:
dfs_graph(g, v, seen, order)
Java
void dfsGraph(
Map<Integer, List<Integer>> g,
int u, Set<Integer> seen,
List<Integer> order) {
seen.add(u);
order.add(u);
for (int v : g.get(u)) {
if (!seen.contains(v))
dfsGraph(g, v, seen, order);
}
}
Template 5 · 2D grid: BFS
Visited rule: keep a seen matrix the same size as the grid, and set it on push, before the cell ever enters the queue. DIRS is up, down, left, right; add diagonals only if the question says so.
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs_grid(grid, sr, sc):
R, C = len(grid), len(grid[0])
seen = [[False] * C for _ in range(R)]
seen[sr][sc] = True
q = deque([(sr, sc)])
while q:
r, c = q.popleft() # process (r, c) here
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if not (0 <= nr < R and 0 <= nc < C): # off the board
continue
if seen[nr][nc] or grid[nr][nc] == 1: # seen, or a wall
continue
seen[nr][nc] = True
q.append((nr, nc))
int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void bfsGrid(int[][] grid, int sr, int sc) {
int R = grid.length, C = grid[0].length;
boolean[][] seen = new boolean[R][C];
Queue<int[]> q = new ArrayDeque<>();
seen[sr][sc] = true;
q.add(new int[]{sr, sc});
while (!q.isEmpty()) {
int[] cell = q.poll();
int r = cell[0], c = cell[1];
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (seen[nr][nc] || grid[nr][nc] == 1) continue;
seen[nr][nc] = true;
q.add(new int[]{nr, nc});
}
}
}
Template 6 · 2D grid: DFS
Visited rule: same seen matrix, marked on entry. In grid DFS the "push" is the recursive call, so mark the cell in the first three lines of the function, before you call the neighbours.
def dfs_grid(grid, r, c, seen, order):
R, C = len(grid), len(grid[0])
if not (0 <= r < R and 0 <= c < C):
return
if seen[r][c] or grid[r][c] == 1:
return
seen[r][c] = True # mark on entry, never later
order.append((r, c))
for dr, dc in DIRS:
dfs_grid(grid, r + dr, c + dc, seen, order)
void dfsGrid(int[][] grid, int r, int c, boolean[][] seen) {
int R = grid.length, C = grid[0].length;
if (r < 0 || r >= R || c < 0 || c >= C) return;
if (seen[r][c] || grid[r][c] == 1) return;
seen[r][c] = true;
for (int[] d : DIRS) {
dfsGrid(grid, r + d[0], c + d[1], seen);
}
}
On the grid below, starting at (0,0) with 1 = wall, BFS visits (0,0) (1,0) (0,1) (2,0) (0,2) (2,1) (1,2) (2,2) and DFS visits (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1). Same eight cells, different order.
0 0 0 BFS: rings around the start
0 1 0 DFS: down the left wall, then round
0 0 0
Which one, and when
Use BFS when
Shortest path in an unweighted graph or grid. BFS finds the target at its true minimum number of steps, because it finishes every distance-k node before it touches any distance-(k+1) node.
Level order. Anything phrased as "level by level", "nearest first", "minimum number of moves", "fewest steps".
Very deep inputs. A queue lives on the heap, so BFS will not blow the call stack.
Use DFS when
Any path will do. "Is there a route from A to B", "can this be coloured", "print all paths".
Cycle detection. DFS remembers the path it is on, which is exactly what a cycle check needs.
Connected components and flood fill. Count islands, fill a region, group friends. Four lines of recursion and done.
Both visit every node and every edge once, so both are O(V + E) in time. Memory is where they differ: BFS holds a whole level in the queue, DFS holds one path on the stack. On a wide, shallow graph DFS uses less memory. On a narrow, deep one BFS does.
If the question contains the word "shortest" and the edges have no weights, write BFS. If it asks "does a path exist" or "how many groups", write DFS. That single rule answers most interview questions in this topic.
Worked problem 1 · Easy
Level order of a binary tree
Return the values level by level, as a list of lists. The trick is one line: freeze the queue size before the level starts, then pop exactly that many nodes. Whatever you push during the level belongs to the next level.
def level_order(root):
if not root:
return []
out = []
q = deque([root])
while q:
size = len(q) # freeze it here
level = []
for _ in range(size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(level)
return out
Trace on the tree 1 / 2 3 / 4 5 6 · output [[1], [2, 3], [4, 5, 6]]
queue [1] size 1 -> level [1] queue now [2, 3]
queue [2, 3] size 2 -> level [2, 3] queue now [4, 5, 6]
queue [4, 5, 6] size 3 -> level [4, 5, 6] queue now []
Worked problem 2 · Medium
Number of islands
A grid of "1" (land) and "0" (water). Count the groups of land joined up, down, left or right. Walk every cell; the first time you stand on land, that is a new island, so count it and sink the whole island so it is never counted twice.
def sink(grid, r, c):
if not (0 <= r < len(grid) and 0 <= c < len(grid[0])):
return
if grid[r][c] != "1":
return
grid[r][c] = "0" # marking visited = sinking the land
sink(grid, r + 1, c)
sink(grid, r - 1, c)
sink(grid, r, c + 1)
sink(grid, r, c - 1)
def num_islands(grid):
count = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == "1":
count += 1
sink(grid, r, c)
return count
Trace · answer 3
1 1 0 0 island 1 starts at (0,0), sinks (0,0) (1,0) (1,1) (0,1)
1 1 0 0 island 2 starts at (2,2), sinks (2,2)
0 0 1 0 island 3 starts at (3,3), sinks (3,3)
0 0 0 1 every other cell is already "0" when the scan reaches it
Worked problem 3 · Medium
Shortest path with obstacles
0 is open, 1 is a wall. Fewest steps from the top-left to the bottom-right, moving up, down, left or right. Carry the distance in the queue and return the moment you pop the target: BFS guarantees that is the smallest possible distance.
def shortest_path(grid):
R, C = len(grid), len(grid[0])
if grid[0][0] == 1 or grid[R - 1][C - 1] == 1:
return -1
seen = {(0, 0)}
q = deque([(0, 0, 0)]) # row, col, steps so far
while q:
r, c, d = q.popleft()
if r == R - 1 and c == C - 1:
return d
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if not (0 <= nr < R and 0 <= nc < C):
continue
if grid[nr][nc] == 1 or (nr, nc) in seen:
continue
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return -1 # queue empty, target unreachable
Trace · the frontier at each distance · answer 6
0 0 1 0 d=0 (0,0) d=4 (2,0) (2,2)
1 0 1 0 d=1 (0,1) d=5 (3,0) (2,3)
0 0 0 0 d=2 (1,1) d=6 (1,3) (3,3) <- target, return 6
0 1 1 0 d=3 (2,1)
Why not DFS here? DFS would also find the exit, but the first route it stumbles on is almost never the shortest, so you would have to try every route and keep the minimum. BFS pops cells in distance order, so the first time it touches the exit it is already the answer.
Worked problem 4 · Medium
Cycle in an undirected graph
In an undirected graph every edge points both ways, so 0 to 1 and back to 0 is not a cycle. Carry the parent: a neighbour that is already seen and is not the node you came from means you have arrived twice at the same node by two different routes, which is a cycle.
def has_cycle(g):
seen = set()
def dfs(u, parent):
seen.add(u)
for v in g[u]:
if v == parent: # the edge we just came along
continue
if v in seen:
return True
if dfs(v, u):
return True
return False
for node in g: # the graph may be in pieces
if node not in seen:
if dfs(node, -1):
return True
return False
Trace · g1 = {0:[1,2], 1:[0,2], 2:[0,1], 3:[4], 4:[3]} · answer True
visit 0, parent -1 seen {0}
visit 1, parent 0 seen {0,1}
visit 2, parent 1 seen {0,1,2} neighbour 0 is seen and is not the parent -> True
On g2 = {0:[1,2], 1:[0], 2:[0,3], 3:[2]} the same run visits 0, 1, 2, 3, never meets a seen non-parent, and returns False. That graph is a tree.
The 5 mistakes
- 1
No visited set on a graphThe code runs forever, or the online judge says "time limit exceeded" on a graph with any cycle at all. A tree needs no visited set; anything else does.
- 2
Marking visited when you pop instead of when you pushThe classic. Node 5 is a neighbour of 2 and of 3, so it enters the queue twice before it is popped once. Your answer is still right, the queue is twice the size, and on a big grid you time out.
- 3
Recursive DFS on a very deep inputPython stops at about 1000 nested calls: RecursionError. Java throws StackOverflowError. On a 1000 by 1000 grid that is a real risk. Switch to the iterative version with an explicit stack, or use BFS.
- 4
Changing the queue while walking a levelIn level order, read the size into a variable first. If you write for i in range(len(q)) and push inside the loop, the level never ends the way you expect and levels blur together.
- 5
Wrong neighbour offsets on a gridWriting (r+1, c+1) for "down" instead of (r+1, c). Keep one DIRS list at the top and never type the four offsets inline. Add the four diagonals only when the question says diagonals count.
Test yourself in 60 seconds: close this file, open a blank editor, and type the graph BFS template. If the visited set lands in the same two lines as the queue push, you have it.