Tree Traversals in Python: DFS, BFS and Grid Problems

Trees and graphs appear in a large share of coding interviews. Almost every problem reduces to one decision: do you explore deep first (DFS) or level by level (BFS)? This guide shows both, then applies DFS to a grid.

The tree node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Depth-first search with recursion

DFS follows one branch to the end before backing up. Inorder traversal visits the left subtree, then the node, then the right subtree. For a binary search tree this produces the values in sorted order.

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

Time is O(n) because every node is visited once. Space is O(h) for the recursion stack, where h is the height of the tree: O(log n) for a balanced tree and O(n) for a skewed one.

Breadth-first search with a queue

BFS visits all nodes at depth 1, then depth 2, and so on. It uses a queue. Processing one level at a time by reading the queue length first gives you the Level Order Traversal answer.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            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 result

Which one should you choose?

• Use BFS for shortest path in an unweighted graph or anything described by levels.
• Use DFS for exploring all possibilities, path problems, and when recursion makes the code shorter.

The same idea on a grid: Number of Islands

A grid is just a graph where each cell connects to its four neighbours. To count islands of '1' cells, scan the grid. When you find land, count one island and use DFS to turn the whole island into water so it is not counted again.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

Time is O(rows x cols) and extra space is O(rows x cols) in the worst case for the recursion stack. Python limits recursion depth, so for very large grids switch to an explicit stack or BFS and say so in your interview.