Depth-First Search (DFS) Pattern¶

Overview¶

Explore as deep as possible before backtracking. Uses recursion or explicit stack. Ideal for exhaustive search, path finding, and tree/graph traversal.

When to Use¶

Tree traversals (preorder, inorder, postorder)
Path finding (all paths, any path exists)
Cycle detection
Connected components
Topological sort
Backtracking problems
Island counting/exploration

DFS vs BFS Traversal Order

Template Code¶

Basic DFS on Graph (Recursive)¶

public void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
    visited[node] = true;
    System.out.println("Visited: " + node);

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

Basic DFS on Graph (Iterative)¶

public void dfsIterative(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Stack<Integer> stack = new Stack<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();

        if (!visited[node]) {
            visited[node] = true;
            System.out.println("Visited: " + node);

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

Binary Tree Traversals¶

// Preorder: Root → Left → Right
public void preorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
}

// Inorder: Left → Root → Right (sorted for BST)
public void inorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    inorder(root.left, result);
    result.add(root.val);
    inorder(root.right, result);
}

// Postorder: Left → Right → Root
public void postorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);
}

Number of Islands (Grid DFS)¶

public int numIslands(char[][] grid) {
    int count = 0;
    int m = grid.length, n = grid[0].length;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                dfsIsland(grid, i, j);
                count++;
            }
        }
    }

    return count;
}

private void dfsIsland(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
        || grid[i][j] != '1') {
        return;
    }

    grid[i][j] = '0';  // Mark visited

    dfsIsland(grid, i + 1, j);
    dfsIsland(grid, i - 1, j);
    dfsIsland(grid, i, j + 1);
    dfsIsland(grid, i, j - 1);
}

Path Sum (Root to Leaf)¶

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;

    // Check leaf node
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }

    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) ||
           hasPathSum(root.right, remaining);
}

All Paths from Source to Target¶

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    path.add(0);
    dfs(graph, 0, path, result);
    return result;
}

private void dfs(int[][] graph, int node, List<Integer> path,
                 List<List<Integer>> result) {
    if (node == graph.length - 1) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int neighbor : graph[node]) {
        path.add(neighbor);
        dfs(graph, neighbor, path, result);
        path.remove(path.size() - 1);  // Backtrack
    }
}

Clone Graph¶

public Node cloneGraph(Node node) {
    if (node == null) return null;

    Map<Node, Node> visited = new HashMap<>();
    return dfsClone(node, visited);
}

private Node dfsClone(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) {
        return visited.get(node);
    }

    Node clone = new Node(node.val);
    visited.put(node, clone);

    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfsClone(neighbor, visited));
    }

    return clone;
}

Cycle Detection in Directed Graph¶

public boolean hasCycle(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
    }

    int[] state = new int[n];  // 0=unvisited, 1=visiting, 2=visited

    for (int i = 0; i < n; i++) {
        if (hasCycleDFS(graph, i, state)) {
            return true;
        }
    }

    return false;
}

private boolean hasCycleDFS(List<List<Integer>> graph, int node, int[] state) {
    if (state[node] == 1) return true;   // Back edge - cycle!
    if (state[node] == 2) return false;  // Already processed

    state[node] = 1;  // Mark visiting

    for (int neighbor : graph.get(node)) {
        if (hasCycleDFS(graph, neighbor, state)) {
            return true;
        }
    }

    state[node] = 2;  // Mark visited
    return false;
}

Max Depth of Binary Tree¶

public int maxDepth(TreeNode root) {
    if (root == null) return 0;

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Validate Binary Search Tree¶

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;

    if ((min != null && node.val <= min) ||
        (max != null && node.val >= max)) {
        return false;
    }

    return validate(node.left, min, node.val) &&
           validate(node.right, node.val, max);
}

Lowest Common Ancestor¶

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) {
        return root;  // p and q are in different subtrees
    }

    return left != null ? left : right;
}

Surrounded Regions (Border DFS)¶

public void solve(char[][] board) {
    int m = board.length, n = board[0].length;

    // Mark border-connected 'O's as safe
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') dfs(board, i, 0);
        if (board[i][n-1] == 'O') dfs(board, i, n-1);
    }
    for (int j = 0; j < n; j++) {
        if (board[0][j] == 'O') dfs(board, 0, j);
        if (board[m-1][j] == 'O') dfs(board, m-1, j);
    }

    // Flip: 'O' → 'X', 'S' → 'O'
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == 'S') board[i][j] = 'O';
        }
    }
}

private void dfs(char[][] board, int i, int j) {
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
        || board[i][j] != 'O') {
        return;
    }

    board[i][j] = 'S';  // Mark safe
    dfs(board, i+1, j);
    dfs(board, i-1, j);
    dfs(board, i, j+1);
    dfs(board, i, j-1);
}

Time & Space Complexity¶

Problem	Time	Space
Graph DFS	O(V + E)	O(V)
Tree DFS	O(n)	O(h)
Grid DFS	O(m × n)	O(m × n)
All paths	O(2^n × n)	O(n)
Clone graph	O(V + E)	O(V)

Common Interview Questions¶

Max Depth of Binary Tree - Simple recursion
Same Tree - Compare two trees
Symmetric Tree - Mirror check
Path Sum - Root to leaf sum
Path Sum II - All paths with target sum
Number of Islands - Connected components
Surrounded Regions - Border DFS
Clone Graph - Deep copy with visited map
Validate BST - Range checking
Lowest Common Ancestor - LCA in binary tree
Flatten Binary Tree to Linked List - Preorder flatten
Course Schedule - Cycle detection
Pacific Atlantic Water Flow - Dual DFS
Word Search - Grid backtracking

Tips & Tricks¶

Recursive DFS is cleaner for trees; use stack for graphs
Mark nodes visited before exploring (not after return)
For grids: modify in-place or use visited set
Use 3-state marking for directed cycle detection
Path problems often need backtracking (undo changes)
DFS on tree uses O(h) space; BFS uses O(w) where w is max width