Depth-First Search (DFS) is one of the most fundamental graph traversal algorithms. It works by starting at a node and exploring as far down each branch as possible before backtracking — making it ideal for problems involving reachability, connected components, paths, and tree structure. This page collects ready-to-use Java templates for the most common DFS patterns you’ll encounter on LeetCode. See also Graph and Backtracking.

New to DFS? DFS explores as deep as possible before backtracking. Think of it like exploring a maze — go straight until you hit a dead end, then back up and try the next turn.

DFS Traversal Order 1 ① 2 ② 3 ⑤ 4 ③ 5 ④ 6 ⑥ Stack 3 5 ← top of stack Visited Processing Unvisited DFS goes deep before going wide

Pattern Comparison

| Pattern | When to Use | Time | Space | |—|—|—|—| | Basic DFS | Reachability, connected components | O(V+E) | O(V) | | Grid DFS | Flood fill, island counting | O(M×N) | O(M×N) | | Tree DFS | All tree traversals, path problems | O(N) | O(H) | | DFS + Memo | Overlapping subproblems on graphs/grids | O(States) | O(States) | | Iterative | When recursion stack overflows | O(V+E) | O(V) |

DFS vs BFS

When should you pick DFS over BFS (or vice versa)?

  • Use DFS when you need to explore all paths, check connectivity, detect cycles, or solve problems that decompose recursively (e.g., tree shape, backtracking). DFS is also more memory-efficient on narrow/deep structures.
  • Use BFS when you need the shortest path in an unweighted graph, want to process nodes level by level, or need the minimum number of steps to reach a target.
  • Rule of thumb: If the problem says “shortest” or “minimum steps,” reach for BFS. If it says “all paths,” “connected,” or “exists,” DFS is usually the natural fit.
DFS — Goes deep first A B C D E F ① ② ③ ④ ⑤ ⑥ deep vs BFS — Goes wide first level 1 A B C D E F ① ② ③ ④ ⑤ ⑥ wide

Contents

Basic DFS

Depth-First Search explores as far as possible before backtracking.

When to use: Checking reachability between nodes, finding connected components, or exploring all paths in a general graph.

ID Title Link Solution
841 Keys and Rooms Link Solution 
// DFS on graph (adjacency list)
static void dfs(int[][] graph, int node, boolean[] visited) {
    visited[node] = true;

    // Process node
    cout << node << " ";

    // Explore neighbors
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

// DFS with return value
static boolean dfs(int[][] graph, int node, int target, boolean[] visited) {
    if (node == target) return true;
    visited[node] = true;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor] && dfs(graph, neighbor, target, visited)) {
            return true;
        }
    }

    return false;
}
ID Title Link Solution
841 Keys and Rooms Link Solution

DFS on Grid

DFS for 2D grid problems (connected components, paths).

When to use: Flood-fill problems, island counting, or any task where you explore connected cells in a 2D matrix.

DFS flood fill on a grid 0 1 2 3 4 1 ① 1 ② 0 0 0 0 1 ③ 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 DFS flood fill Start at (0,0), explore all connected 1s: ① (0,0) → go right ② (0,1) → go down ③ (1,1) → no more 1s Backtrack → island done! Explored (flood fill) Land (not yet visited) Water (0) Grid has 2 islands. DFS marks each connected component of 1s.
ID Title Link Solution
200 Number of Islands Link Solution
79 Word Search Link Solution
695 Max Area of Island Link Solution
133 Clone Graph Link Solution
417 Pacific Atlantic Water Flow Link Solution
323 Number of Connected Components Link Solution
547 Number of Provinces Link Solution 
// import java.util.*;
// DFS on 2D grid (4-directional)
static void dfsGrid(char[][]& grid, int i, int j) {
    int m = grid.length, n = grid[0].length;

    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
        return;
    }

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

    // Explore 4 directions dfsGrid = new directions(grid, i + 1, j);
    dfsGrid(grid, i - 1, j);
    dfsGrid(grid, i, j + 1);
    dfsGrid(grid, i, j - 1);
}

// Number of Islands using DFS
static int numIslands(char[][]& grid) {
    int m = grid.length, n = grid[0].length;
    int count = 0;

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

    return count;
}

// Word Search
static boolean dfsWordSearch(char[][]& board, int i, int j, String word, int idx) {
    if (idx == word.size()) return true;
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
    if (board[i].charAt(j) != word.charAt(idx)) return false;

    char temp = board[i].charAt(j);
    board[i].charAt(j) = '#'; // Mark as visited

    List<int[]> dirs = {{0,1\}, \{0,-1\}, \{1,0\}, \{-1,0}}
    for (var e : dirs.entrySet()) {
        if (dfsWordSearch(board, i + dx, j + dy, word, idx + 1)) {
            return true;
        }
    }

    board[i].charAt(j) = temp; // Backtrack
    return false;
}
ID Title Link Solution
200 Number of Islands Link Solution
79 Word Search Link Solution
695 Max Area of Island Link Solution
133 Clone Graph Link Solution
417 Pacific Atlantic Water Flow Link Solution
323 Number of Connected Components Link Solution
547 Number of Provinces Link Solution

DFS on Tree

DFS for tree problems (preorder, inorder, postorder).

When to use: Tree traversals, path-sum problems, computing tree height/diameter, or any recursive tree decomposition.

ID Title Link Solution
100 Same Tree Link Solution
101 Symmetric Tree Link Solution
104 Maximum Depth of Binary Tree Link Solution
111 Minimum Depth of Binary Tree Link Solution
112 Path Sum Link Solution
129 Sum Root to Leaf Numbers Link Solution
226 Invert Binary Tree Link Solution
236 Lowest Common Ancestor Link Solution
437 Path Sum III Link Solution
690 Employee Importance Link Solution 
// Preorder DFS
static void preorder(TreeNode root, int[] result) {
    if (!root) return;
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
}

// Inorder DFS
static void inorder(TreeNode root, int[] result) {
    if (!root) return;
    inorder(root.left, result);
    result.add(root.val);
    inorder(root.right, result);
}

// Postorder DFS
static void postorder(TreeNode root, int[] result) {
    if (!root) return;
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);
}

// Path Sum
static boolean hasPathSum(TreeNode root, int targetSum) {
    if (!root) return false;
    if (!root.left && !root.right) {
        return root.val == targetSum;
    }
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

// Sum Root to Leaf Numbers
static int sumNumbers(TreeNode root, int sum) {
    if (!root) return 0;
    sum = sum 10 + root.val;
    if (!root.left && !root.right) return sum;
    return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
}
ID Title Link Solution
100 Same Tree Link Solution
101 Symmetric Tree Link Solution
104 Maximum Depth of Binary Tree Link Solution
111 Minimum Depth of Binary Tree Link Solution
112 Path Sum Link Solution
129 Sum Root to Leaf Numbers Link Solution
226 Invert Binary Tree Link Solution
236 Lowest Common Ancestor Link Solution
437 Path Sum III Link Solution
690 Employee Importance Link Solution

DFS with Memoization

DFS with caching to avoid recomputation.

When to use: Problems with overlapping subproblems on graphs or grids, such as longest increasing path or counting distinct paths.

DFS with memoization — Longest Increasing Path col 0 col 1 col 2 9 memo=1 9 memo=1 4 memo=2 6 memo=2 6 memo=2 8 memo=1 2 memo=3 1 memo=4 ★ 1 memo=2 Longest increasing path 1 → 2 → 6 → 9 (length 4, shown with arrows) How memo works: memo[r][c] = length of the longest path starting from (r,c) DFS from cell 1 at (2,1): → can go to 2: 1+memo[2][0] → memo[2][0]=3 (2→6→9) → so memo[2][1] = 1+3 = 4 On longest path Path start (max memo)
ID Title Link Solution
329 Longest Increasing Path in a Matrix Link Solution 
// import java.util.*;
// DFS with memoization (e.g., Longest Increasing Path)
static int dfsWithMemo(int[][] matrix, int i, int j,
                int[][] memo, int prev) {
    int m = matrix.length, n = matrix[0].length;

    if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] <= prev) {
        return 0;
    }

    if (memo[i][j] != -1) {
        return memo[i][j];
    }

    int result = 1;
    List<int[]> dirs = {{0,1\}, \{0,-1\}, \{1,0\}, \{-1,0}}
    for (var e : dirs.entrySet()) {
        result = Math.max(result, 1 + dfsWithMemo(matrix, i + dx, j + dy,
                                              memo, matrix[i][j]));
    }

    memo[i][j] = result;
    return result;
}
ID Title Link Solution
329 Longest Increasing Path in a Matrix Link Solution

Iterative DFS

DFS using stack instead of recursion.

When to use: When the recursion depth might cause a stack overflow, or when you need explicit control over the traversal order.

ID Title Link Solution
144 Binary Tree Preorder Traversal Link -
94 Binary Tree Inorder Traversal Link - 
// import java.util.*;
// Iterative DFS on graph
static void dfsIterative(int[][] graph, int start) {
    Deque<Integer> st = new ArrayDeque<>();
    boolean[]visited(graph.size(), false);

    st.offer(start);

    while (!st.isEmpty()) {
        int node = st.peek();
        st.poll();

        if (visited[node]) continue;
        visited[node] = true;

        // Process node
        cout << node << " ";

        // Push neighbors in reverse order to maintain order
        for (int i = graph[node].size() - 1; i >= 0; --i) {
            if (!visited[graph[node][i]]) {
                st.offer(graph[node][i]);
            }
        }
    }
}

// Iterative DFS on tree
int[]preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (!root) return result;

    Deque<TreeNode> st = new ArrayDeque<>();
    st.offer(root);

    while (!st.isEmpty()) {
        TreeNode node = st.peek();
        st.poll();
        result.add(node.val);

        if (node.right) st.offer(node.right);
        if (node.left) st.offer(node.left);
    }

    return result;
}
ID Title Link Solution
144 Binary Tree Preorder Traversal Link -
94 Binary Tree Inorder Traversal Link -

More templates