DFS & BFS

Recursive DFS Template

// Recursive DFS — all three orders in one structure
void dfs(TreeNode node) {
    if (node == null) return;

    // preorder: process node HERE (before children)

    dfs(node.left);

    // inorder: process node HERE (between children)

    dfs(node.right);

    // postorder: process node HERE (after children)
}

Iterative DFS Template (Preorder)

void dfsIterative(TreeNode root) {
    if (root == null) return;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // process node

        if (node.right != null) stack.push(node.right); // right first!
        if (node.left != null) stack.push(node.left);  // so left is popped first
    }
}

BFS Level-Order Template

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();           // nodes at this level
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);         // process node

            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Template: Adjacency List

// DFS on a graph with adjacency list
void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
    visited[node] = true;
    // process node

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

Template: Grid (2D Matrix)

// DFS on a grid — e.g., Number of Islands
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length ||
        c < 0 || c >= grid[0].length ||
        grid[r][c] != '1') return;

    grid[r][c] = '0';                // mark visited

    for (int[] d : dirs) {
        dfs(grid, r + d[0], c + d[1]);
    }
}

Template: Shortest Path in Grid

// BFS shortest path on a grid
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

int shortestPath(int[][] grid, int[] start, int[] end) {
    int rows = grid.length, cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    Queue<int[]> queue = new LinkedList<>();

    queue.offer(start);
    visited[start[0]][start[1]] = true;
    int steps = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();           // all nodes at this distance

        for (int i = 0; i < size; i++) {
            int[] pos = queue.poll();
            if (pos[0] == end[0] && pos[1] == end[1])
                return steps;               // found shortest path!

            for (int[] d : dirs) {
                int nr = pos[0] + d[0], nc = pos[1] + d[1];
                if (nr >= 0 && nr < rows &&
                    nc >= 0 && nc < cols &&
                    !visited[nr][nc] &&
                    grid[nr][nc] != 1) {       // not a wall
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        steps++;
    }
    return -1;  // unreachable
}

Why O(V + E)?

Both DFS and BFS visit every vertex exactly once — that is O(V). For each vertex, they examine all its edges — summed across all vertices, that is O(E). Total: O(V + E).

On a grid (R rows, C cols): V = R * C and each cell has at most 4 edges, so E = O(V). Time becomes O(R * C).

Space: The visited set takes O(V). DFS additionally uses O(V) stack space in the worst case (linear graph). BFS uses O(V) queue space in the worst case (all nodes at same level). Either way: O(V).

Space Differences on Trees