Depth First Search

DFS is Tree/Graph traversal algorithm that explores as far down as possible before backtracking.

How it works

1. Start from the root node
2. Visit the current node and process it
3. Recursively or iteratively explore each of the child nodes
4. Back track when no visitors remain

Binary Trees

def dfs(root):
    if not root:
        return
    
    # --- Preorder (do work before children) ---
    # print(root.val)  # process node
    
    dfs(root.left)
    
    # --- Inorder (do work between children) ---
    # print(root.val)
    
    dfs(root.right)
    
    # --- Postorder (do work after children) ---
    # print(root.val)

Where you process the work in the recursive calls dictates which type of traversal you will do.

Because there are no cycles in a binary tree, we do not need to process nodes that we've seen.

2D Matrix

When traversing a 2D matrix represented as a graph, it is important to make sure our current coordinates are inside the bounds and that we are keeping track of elements we have already seen.

ROWS, COLS = len(grid), len(grid[0])
visit = set()
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def dfs(r, c):
    # 1. Check bounds and visited condition
    if (
        r < 0 or c < 0 or 
        r >= ROWS or c >= COLS or 
        (r, c) in visit
    ):
        return
    
    # 2. Mark as visited
    visit.add((r, c))
    
    # 3. Explore neighbors (up, down, left, right)
	for dr, dc in directions:
		# 4. Add question specific checks where necessary
        dfs(r + dr, c + dc)

for r in range(ROWS):
    for c in range(COLS):
		dfs(r, c)   # 0. Start DFS from this cell