Depth-First Search (DFS)

Definition

A graph traversal algorithm that explores as far as possible along each branch before backtracking. Uses a STACK (explicit or call stack).

Key Properties: - Explores depth before breadth - Uses Stack (recursion or explicit) - Memory efficient for deep graphs - Good for path finding, cycle detection

DFS vs BFS: DFS = Deep before wide (children before siblings) | BFS = Wide before deep (siblings before children)

---

Big O Complexity

---

When to Use

---

Recursive vs Iterative

---

Implementation

Recursive DFS - Graph

public void dfsRecursive(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    dfs(graph, start, visited);
}

private void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
    visited.add(node);
    System.out.print(node + " ");

    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

Iterative DFS - Graph

public void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();

    stack.push(start);

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

        if (visited.contains(node)) continue;

        visited.add(node);
        System.out.print(node + " ");

        // Add neighbors in reverse for same order as recursive
        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            if (!visited.contains(neighbors.get(i))) {
                stack.push(neighbors.get(i));
            }
        }
    }
}

Tree Traversals (Recursive)

// Preorder: Root → Left → Right
public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

// Inorder: Left → Root → Right
public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

// Postorder: Left → Right → Root
public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

Tree Traversals (Iterative)

// Iterative Preorder
public List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);

        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }

    return result;
}

// Iterative Inorder
public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }

    return result;
}

// Iterative Postorder (using two stacks)
public List<Integer> postorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);

    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);

        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }

    while (!stack2.isEmpty()) {
        result.add(stack2.pop().val);
    }

    return result;
}

---

Common Problems

Cycle Detection - Undirected Graph

public boolean hasCycleUndirected(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();

    for (int node : graph.keySet()) {
        if (!visited.contains(node)) {
            if (dfsCycleUndirected(graph, node, -1, visited)) {
                return true;
            }
        }
    }

    return false;
}

private boolean dfsCycleUndirected(Map<Integer, List<Integer>> graph,
                                    int node, int parent, Set<Integer> visited) {
    visited.add(node);

    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            if (dfsCycleUndirected(graph, neighbor, node, visited)) {
                return true;
            }
        } else if (neighbor != parent) {
            return true;  // Back edge found
        }
    }

    return false;
}

Cycle Detection - Directed Graph

public boolean hasCycleDirected(Map<Integer, List<Integer>> graph, int numNodes) {
    int[] state = new int[numNodes];  // 0=unvisited, 1=visiting, 2=visited

    for (int i = 0; i < numNodes; i++) {
        if (state[i] == 0) {
            if (dfsCycleDirected(graph, i, state)) {
                return true;
            }
        }
    }

    return false;
}

private boolean dfsCycleDirected(Map<Integer, List<Integer>> graph,
                                  int node, int[] state) {
    state[node] = 1;  // Visiting

    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (state[neighbor] == 1) return true;  // Back edge
        if (state[neighbor] == 0 && dfsCycleDirected(graph, neighbor, state)) {
            return true;
        }
    }

    state[node] = 2;  // Visited
    return false;
}

Topological Sort

public List<Integer> topologicalSort(Map<Integer, List<Integer>> graph, int numNodes) {
    boolean[] visited = new boolean[numNodes];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < numNodes; i++) {
        if (!visited[i]) {
            dfsTopological(graph, i, visited, stack);
        }
    }

    List<Integer> result = new ArrayList<>();
    while (!stack.isEmpty()) {
        result.add(stack.pop());
    }
    return result;
}

private void dfsTopological(Map<Integer, List<Integer>> graph,
                            int node, boolean[] visited, Stack<Integer> stack) {
    visited[node] = true;

    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited[neighbor]) {
            dfsTopological(graph, neighbor, visited, stack);
        }
    }

    stack.push(node);  // Add after all descendants
}

Number of Islands (Grid DFS)

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int count = 0;
    int rows = grid.length, cols = grid[0].length;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }

    return count;
}

private void dfs(char[][] grid, int row, int col) {
    if (row < 0 || row >= grid.length ||
        col < 0 || col >= grid[0].length ||
        grid[row][col] == '0') {
        return;
    }

    grid[row][col] = '0';  // Mark visited

    dfs(grid, row + 1, col);
    dfs(grid, row - 1, col);
    dfs(grid, row, col + 1);
    dfs(grid, row, col - 1);
}

Path Exists in Graph

public boolean validPath(int n, int[][] edges, int source, int destination) {
    Map<Integer, List<Integer>> graph = new HashMap<>();

    for (int[] edge : edges) {
        graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
    }

    Set<Integer> visited = new HashSet<>();
    return dfs(graph, source, destination, visited);
}

private boolean dfs(Map<Integer, List<Integer>> graph,
                    int current, int target, Set<Integer> visited) {
    if (current == target) return true;

    visited.add(current);

    for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            if (dfs(graph, neighbor, target, visited)) {
                return true;
            }
        }
    }

    return false;
}

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 dfs(node, visited);
}

private Node dfs(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(dfs(neighbor, visited));
    }

    return clone;
}

---

Backtracking Template

// General backtracking pattern using DFS
void backtrack(State state, List<Solution> result) {
    if (isGoal(state)) {
        result.add(state.copy());
        return;
    }

    for (Choice choice : getChoices(state)) {
        if (isValid(choice, state)) {
            makeChoice(choice, state);     // Apply
            backtrack(state, result);
            undoChoice(choice, state);     // Undo (backtrack)
        }
    }
}

N-Queens Example

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');

    backtrack(board, 0, result);
    return result;
}

private void backtrack(char[][] board, int row, List<List<String>> result) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }

    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(board, row + 1, result);
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

---

Tips & Tricks

---