Depth-First Search

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Think of it like exploring a maze - you keep going forward down one path until you hit a dead end, then you backtrack and try a different path.

Imagine you're in a library looking for a specific book. Instead of checking every shelf systematically, you go deep into one aisle, explore all its sections completely, then come back and try the next aisle. That's DFS!

How Does It Work?

DFS uses a stack (or recursion, which uses the call stack) to remember where to go back to. Here's the simple process:

  1. Start at the root (or any starting node)
  2. Mark the current node as visited
  3. Explore one of its unvisited neighbors
  4. Go as deep as possible down that path
  5. When you hit a dead end (no unvisited neighbors), backtrack
  6. Repeat until all reachable nodes are visited

Real-Life Example

Let's explore this graph using DFS starting from node A:

        A
       / \
      B   C
     /   / \
    D   E   F

DFS Traversal Order: A → B → D → C → E → F

Step by step:

  1. Start at A, mark it visited
  2. Go to B (A's first child), mark it visited
  3. Go to D (B's only child), mark it visited
  4. D has no children, backtrack to B
  5. B has no more unvisited children, backtrack to A
  6. Go to C (A's second child), mark it visited
  7. Go to E (C's first child), mark it visited
  8. E has no children, backtrack to C
  9. Go to F (C's second child), mark it visited
  10. Done! All nodes visited

Visual Representation

Step 1: Visit A          Step 2: Visit B          Step 3: Visit D
   [A]                      [A]                      [A]
   / \                      / \                      / \
  B   C                   [B]  C                   [B]  C
 /   / \                  /   / \                 [D]  / \
D   E   F                D   E   F                    E   F

Step 4-6: Backtrack      Step 7: Visit E          Step 8: Visit F
   [A]                      [A]                      [A]
   / \                      / \                      / \
 [B] [C]                  [B] [C]                  [B] [C]
 [D] / \                  [D] / \                  [D] / \
    E   F                    [E]  F                   [E] [F]

Final: A → B → D → C → E → F

Code Implementation

import java.util.*;

class Graph {
private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(v).add(w);
    }

    // Recursive DFS
    public void dfsRecursive(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsRecursiveHelper(start, visited);
    }

    private void dfsRecursiveHelper(int node, Set<Integer> visited) {
        // Mark current node as visited
        visited.add(node);
        System.out.print(node + " ");

        // Recursively visit all unvisited neighbors
        if (adjList.containsKey(node)) {
            for (int neighbor : adjList.get(node)) {
                if (!visited.contains(neighbor)) {
                    dfsRecursiveHelper(neighbor, visited);
                }
            }
        }
    }

    // Iterative DFS using Stack
    public void dfsIterative(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)) {
                visited.add(node);
                System.out.print(node + " ");

                // Push all unvisited neighbors to stack
                if (adjList.containsKey(node)) {
                    // Reverse order to maintain left-to-right traversal
                    List<Integer> neighbors = adjList.get(node);
                    for (int i = neighbors.size() - 1; i >= 0; i--) {
                        if (!visited.contains(neighbors.get(i))) {
                            stack.push(neighbors.get(i));
                        }
                    }
                }
            }
        }
    }

}

Time and Space Complexity

Time Complexity: O(V + E)

  • V = number of vertices (nodes)
  • E = number of edges
  • We visit each vertex once and explore each edge once

Space Complexity:

  • Recursive: O(V) - for the call stack (can be O(h) where h is height for trees)
  • Iterative: O(V) - for the explicit stack
  • Both also need O(V) for the visited set

DFS vs BFS Comparison

FeatureDFSBFS
Data StructureStack (or recursion)Queue
TraversalGo deep firstGo wide first
MemoryLess memory (goes deep)More memory (stores level)
Path FindingMay not find shortest pathAlways finds shortest path
Best ForTopological sorting, cycle detectionShortest path, level-order

Applications of DFS

  1. Pathfinding - Finding if a path exists between two nodes
  2. Cycle Detection - Detecting cycles in a graph
  3. Topological Sorting - Ordering tasks with dependencies
  4. Connected Components - Finding disconnected parts of a graph
  5. Maze Solving - Finding a way out of a maze
  6. Tree Traversal - Preorder, Inorder, Postorder traversals
  7. Backtracking Problems - Sudoku, N-Queens, etc.

When to Use DFS?

Use DFS when:

  • You need to visit all nodes (complete traversal)
  • Memory is limited (DFS uses less memory than BFS)
  • You're solving backtracking problems
  • You need to detect cycles
  • You're doing topological sorting
  • The solution is far from the root

Don't use DFS when:

  • You need the shortest path (use BFS instead)
  • The tree/graph is very deep (risk of stack overflow)
  • You need level-by-level traversal

Recursive vs Iterative DFS

Recursive (Recommended for simplicity):

  • Cleaner and easier to write
  • Uses implicit call stack
  • Can cause stack overflow for very deep graphs
  • More intuitive for tree problems

Iterative (Recommended for deep graphs):

  • More control over the stack
  • No risk of stack overflow
  • Uses explicit stack
  • Slightly more code but safer for production

Advantages and Disadvantages

Advantages:

  • Memory efficient (uses less memory than BFS)
  • Simple to implement recursively
  • Perfect for exploring all paths
  • Great for backtracking problems
  • Works well for trees and graphs

Disadvantages:

  • May not find the shortest path
  • Can get stuck in infinite loops if not careful with visited set
  • Stack overflow risk with recursive implementation
  • Doesn't work well for weighted graphs (use Dijkstra's)

Common Variations

1. DFS on Binary Tree (Preorder)

void dfsPreorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");  // Process
    dfsPreorder(root.left);            // Left
    dfsPreorder(root.right);           // Right
}

2. DFS with Path Tracking

void dfsWithPath(int node, Set<Integer> visited, List<Integer> path) {
    visited.add(node);
    path.add(node);

    for (int neighbor : graph.get(node)) {
        if (!visited.contains(neighbor)) {
            dfsWithPath(neighbor, visited, path);
        }
    }
}

3. DFS for Cycle Detection

boolean hasCycle(int node, Set<Integer> visited, Set<Integer> recStack) {
    visited.add(node);
    recStack.add(node);

    for (int neighbor : graph.get(node)) {
        if (!visited.contains(neighbor)) {
            if (hasCycle(neighbor, visited, recStack)) return true;
        } else if (recStack.contains(neighbor)) {
            return true;  // Cycle detected
        }
    }

    recStack.remove(node);
    return false;
}

Must-Do LeetCode Questions

#ProblemDifficultyLink
1Number of IslandsMediumLeetCode 200
2Clone GraphMediumLeetCode 133
3Path SumEasyLeetCode 112
4Binary Tree PathsEasyLeetCode 257
5Flood FillEasyLeetCode 733
6Course ScheduleMediumLeetCode 207
7Course Schedule IIMediumLeetCode 210
8Pacific Atlantic Water FlowMediumLeetCode 417
9Max Area of IslandMediumLeetCode 695
10All Paths From Source to TargetMediumLeetCode 797
11Surrounded RegionsMediumLeetCode 130
12Number of ProvincesMediumLeetCode 547
13Keys and RoomsMediumLeetCode 841
14Network Delay TimeMediumLeetCode 743
15Word SearchMediumLeetCode 79

Common Mistakes to Avoid

  1. Forgetting the visited set - Leads to infinite loops
  2. Not handling disconnected components - Some nodes may never be reached
  3. Stack overflow with deep recursion - Use iterative for very deep graphs
  4. Wrong base case in recursion - Always check for null/invalid nodes
  5. Not restoring state in backtracking - Remember to remove from visited set when needed

DFS Template (Recursive)

function dfs(node, visited):
    if node is null or node in visited:
        return

    visited.add(node)
    // Process current node

    for each neighbor of node:
        if neighbor not in visited:
            dfs(neighbor, visited)

DFS Template (Iterative)

function dfs(start):
    visited = empty set
    stack = [start]

    while stack is not empty:
        node = stack.pop()

        if node not in visited:
            visited.add(node)
            // Process current node

            for each neighbor of node:
                if neighbor not in visited:
                    stack.push(neighbor)

Summary

Depth First Search is one of the most fundamental graph algorithms. It explores as deep as possible before backtracking, making it perfect for problems that require exploring all paths, detecting cycles, or solving backtracking puzzles. While it doesn't guarantee the shortest path like BFS, its simplicity and memory efficiency make it invaluable for many problems.

Key Takeaway: DFS goes deep into one path before exploring other paths. It uses a stack (or recursion) and is essential for tree traversals, backtracking problems, cycle detection, and topological sorting. Always remember to track visited nodes to avoid infinite loops!