Recursion, Trees and Graphs Made Simple (BFS, DFS and When to Use Them)
By Gokul · · 6 min read
Trees and graphs come up in almost every placement test, and most of the fear around them comes from recursion, not the data structure itself. Once the recursion mental model clicks, tree and graph problems become a matter of picking BFS or DFS and writing a few lines around it.
In short: trust recursion to handle the smaller subproblem for you, use DFS when you need to go deep or explore every path, and use BFS when you need the shortest path or a level-by-level view.
The Recursion Mental Model
Recursion feels confusing when you try to trace every call in your head. Instead, trust two things: a base case that stops the recursion, and the assumption that the recursive call already solves the smaller version of the problem correctly.
Base case: the simplest input, where the answer is obvious, such as an empty node or an empty array.
Recursive case: assume the recursive call on a smaller input already works, and use its result to build the answer for the current input.
Here is factorial written with that mindset. Trust that factorial(n - 1) already returns the correct answer for n - 1.
Python
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # trust the smaller callEvery call adds a frame to the call stack, and each frame waits for the one below it to return. That stack is also why very deep recursion, such as over a very large linked list, can cause a stack overflow, which is worth remembering for edge cases.
Binary Tree Traversals
A binary tree traversal visits every node once, and the three common orders differ only in when you visit the current node relative to its two children.
Preorder (node, left, right): used to copy or serialize a tree.
Inorder (left, node, right): visits a binary search tree in sorted order.
Postorder (left, right, node): used when children must be processed before the parent, such as deleting a tree.
Python – all three traversals
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder(node, out):
if not node:
return
out.append(node.val) # node
preorder(node.left, out) # left
preorder(node.right, out) # right
def inorder(node, out):
if not node:
return
inorder(node.left, out) # left
out.append(node.val) # node
inorder(node.right, out) # right
def postorder(node, out):
if not node:
return
postorder(node.left, out) # left
postorder(node.right, out) # right
out.append(node.val) # nodeBFS vs DFS, With a Diagram
Both BFS and DFS visit every reachable node, but in a different order and using a different structure to track what to visit next.
BFS (breadth-first search) visits level by level, using a queue. It is the standard choice for shortest path in an unweighted graph or grid.
DFS (depth-first search) goes as deep as possible before backtracking, using a stack or recursion. It suits exploring every path, connected components, and problems like cycle detection.
Grid Problems: Islands and Shortest Path
Grid problems are graphs in disguise, where each cell is a node connected to its up, down, left and right neighbours.
Number of Islands (DFS or BFS)
Given a grid of 1s (land) and 0s (water), count the number of islands, where an island is a group of connected 1s. The idea: scan every cell, and whenever you find an unvisited 1, run a DFS or BFS to mark the whole island as visited, and count that as one island.
Python – DFS approach
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return countShortest Path in a Grid (BFS)
To find the shortest path from a start cell to a target cell in an unweighted grid, BFS is the right tool, because it explores cells in increasing order of distance.
Python – BFS approach
from collections import deque
def shortest_path(grid, start, target):
rows, cols = len(grid), len(grid[0])
queue = deque([(start[0], start[1], 0)]) # row, col, distance
visited = {start}
while queue:
r, c, dist = queue.popleft()
if (r, c) == target:
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] != '0' and (nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1 # target not reachableTypical Interview and OA Questions
Recursion: factorial, Fibonacci, sum of digits, power of a number.
Tree traversals: print or return inorder/preorder/postorder, level order traversal, maximum depth of a tree, validate a binary search tree.
BFS/DFS on graphs: number of connected components, cycle detection, course schedule style dependency problems.
Grids: number of islands, flood fill, shortest path in a maze, rotting oranges style multi-source BFS.
Practice Problems
These three cover the core ideas above. Try each one yourself before checking the outline.
1. Level Order Traversal
Return the values of a binary tree level by level, which is exactly BFS starting from the root, tracking how many nodes are in the current level.
Python
from collections import deque
def level_order(root):
if not root:
return []
result, queue = [], deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result2. Number of Islands
Covered above. Try the BFS version yourself as practice: replace the recursive DFS with a queue, and mark cells visited as you enqueue them instead of when you dequeue them.
3. Validate BST
Check whether a binary tree is a valid binary search tree. A common mistake is comparing only a node to its direct children. Instead, pass down a valid range for each node.
Python
def is_valid_bst(node, low=float('-inf'), high=float('inf')):
if not node:
return True
if not (low < node.val < high):
return False
return (is_valid_bst(node.left, low, node.val)
and is_valid_bst(node.right, node.val, high))Key Takeaways
Trust the base case and the recursive call. You do not need to trace every frame by hand.
Preorder, inorder and postorder differ only in when you visit the current node.
BFS uses a queue and explores level by level. It is the standard choice for shortest path.
DFS uses a stack or recursion and goes deep first. It suits exploring components and paths.
Grid problems are graphs where each cell connects to its neighbours, so tree and graph techniques apply directly.
Test Yourself Under Real Conditions
Reading about BFS and DFS is different from applying them under a timer. Take a timed skill test on Skillrank to see how you handle tree and graph questions when the clock is running.