Depth-First Search (DFS) - Complete Guide with Recursive and Iterative Approaches

What is Depth-First Search (DFS)?

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It follows the depth of the tree/graph, going deep into nodes before visiting siblings.

Why Do Interviewers Love DFS?

1. Tests Recursive Thinking: DFS is naturally implemented with recursion, testing your understanding
2. Broad Applications: Used in trees, graphs, backtracking, dynamic programming, and more
3. Rich Variations: Can extend to numerous problems (path finding, islands, subsets, etc.)
4. Optimization Opportunities: Tests recursion-to-iteration conversion, pruning, etc.

DFS vs BFS Comparison

Feature	DFS (Depth-First)	BFS (Breadth-First)
Traversal Order	Go deep first, then backtrack	Level by level
Data Structure	Stack or Recursion	Queue
Space Complexity	O(h) - tree height	O(w) - widest level
Use Cases	Path finding, topological sort, cycle detection	Shortest path, level-order traversal
Implementation	Recursion simple, iteration moderate	Iteration simple

Core Concept: Depth-First Traversal Strategy

The core idea of DFS can be summarized in one sentence:

Go as deep as you can, backtrack when stuck

DFS Traversal Example:
        1
       / \
      2   3
     / \   \
    4   5   6

Recursive DFS Order: 1 -> 2 -> 4 (backtrack) -> 5 (backtrack) -> 3 -> 6

Three Key Steps of DFS

1. Visit Current Node: Process current node’s logic
2. Recurse on Children: Apply DFS to all child nodes
3. Backtrack: After children are processed, return to parent

Interactive DFS Visualization

The visualizer below demonstrates DFS in different problem contexts. You can select different problems and implementation methods to observe the DFS execution step-by-step.

Problem:Symmetric TreePath SumMax Depth

Method:RecursiveIterative

Use Asymmetric Tree

ResetPreviousReplayNext

Speed:0.5x1x2x

Step 1 of 0

Legend:

Unvisited

Current/Visiting

Comparing

Visited

Found/Match

How to Use:

• Select different Problem Types: Symmetric Tree, Path Sum, Max Depth
• Choose Implementation Method: Recursive or Iterative
• Use Play button to watch the complete DFS process
• Use Previous/Next buttons to examine each step carefully
• View Call Stack/Queue states to understand execution

DFS Universal Template

The key to mastering DFS is memorizing this universal template. 90% of DFS problems can be solved with this pattern.

JavaPythonJavaScript

Loading...

Template Key Points:

1. Three Essentials of Recursion:

   • Termination condition (when to stop)
   • Processing logic (what to do)
   • Recursive calls (how to go deeper)

2. Iterative Key Points:

   • Use stack to simulate recursion
   • Pay attention to push order (right first, left second)

3. Backtracking Timing:

   • Use when state needs restoration
   • Typical scenarios: combinations, permutations, subsets

Classic Problem 1: Symmetric Tree

Symmetric Tree (LC 101)

Problem Description

Given a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example:

    1
   / \
  2   2
 / \ / \
3  4 4  3  ✓ Symmetric

    1
   / \
  2   2
   \   \
   3    3  ✗ Not Symmetric

Solution Approach

Core Insight: A tree is symmetric ⟺ Left and right subtrees are mirrors

Two trees are mirrors if:

1. Root values are the same
2. Left subtree of A mirrors right subtree of B (outer pair)
3. Right subtree of A mirrors left subtree of B (inner pair)

Mirror Comparison Diagram:
    Left        Right
     2            2
    / \          / \
   3   4        4   3
   ↓   ↓        ↓   ↓
   Outer: 3 vs 3 ✓
   Inner: 4 vs 4 ✓

Solution 1: Recursive (Recommended)

JavaPythonJavaScript

Loading...

Complexity Analysis:

• Time Complexity: $O(n)$, visit all nodes
• Space Complexity: $O(h)$, recursion stack depth is tree height, worst case $O(n)$

Solution 2: Iterative (Queue)

JavaPythonJavaScript

Loading...

Complexity Analysis:

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$, queue stores at most one level of nodes

Key Points

✅ Correct Comparison Order (Mirror):

isMirror(left.left, right.right)   // Outer pair
isMirror(left.right, right.left)   // Inner pair

❌ Wrong Comparison Order (Same):

isMirror(left.left, right.left)    // This checks if trees are same, not mirrors!
isMirror(left.right, right.right)

Classic Problem 2: Path Sum

Path Sum (LC 112)

Problem Description

Given a binary tree and a target sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the target sum.

Example:

        5
       / \
      4   8
     /   / \
    11  13  4
   / \       \
  7   2       1

targetSum = 22
Path: 5 -> 4 -> 11 -> 2 = 22 ✓

Solution Approach

This is a典型 DFS + Backtracking problem:

1. Recursive Definition: hasPathSum(node, remaining) returns whether there’s a path from node with sum equal to remaining
2. Recurrence Relation: hasPathSum(node, remaining) = hasPathSum(node.left, remaining - node.val) || hasPathSum(node.right, remaining - node.val)
3. Termination Condition: At leaf node, check if remaining == node.val

JavaPythonJavaScript

Loading...

Complexity Analysis:

• Time Complexity: $O(n)$, worst case visit all nodes
• Space Complexity: $O(h)$, recursion stack depth

Problem Variations

• Path Sum II (LC 113): Return all paths (requires backtracking)
• Path Sum III (LC 437): Path doesn’t need to start from root (double recursion)

Classic Problem 3: Maximum Depth of Binary Tree

Maximum Depth of Binary Tree (LC 104)

Problem Description

Given a binary tree, find its maximum depth. The depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example:

    3
   / \
  9  20
    /  \
   15   7

Max Depth = 3

Solution Approach

This is the most classic bottom-up DFS problem:

Recursive Definition:

$$\text{maxDepth}(node) = \begin{cases} 0 & \text{if node is null} \\ 1 + \max(\text{maxDepth}(left), \text{maxDepth}(right)) & \text{otherwise} \end{cases}$$

JavaPythonJavaScript

Loading...

Complexity Analysis:

• Time Complexity: $O(n)$
• Space Complexity: $O(h)$

Similar Problems

This template can solve many “tree property” problems:

Problem	Recurrence Formula
Minimum Depth	1 + min(left, right) (watch out for leaf nodes)
Count Nodes	1 + count(left) + count(right)
Is Balanced	abs(left - right) <= 1 && balanced(left) && balanced(right)
Diameter	max(left + right, diameter(left), diameter(right))

More Classic DFS Problems

1. Number of Islands (LC 200)

// DFS + Mark Visited
public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    // Boundary check
    if (i < 0 || i >= grid.length || 
        j < 0 || j >= grid[0].length || 
        grid[i][j] == '0') {
        return;
    }
    
    // Mark as visited
    grid[i][j] = '0';
    
    // DFS in four directions
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

2. Binary Tree Paths (LC 257)

// DFS + Backtracking
public List<String> binaryTreePaths(TreeNode root) {
    List<String> result = new ArrayList<>();
    if (root == null) return result;
    
    dfs(root, String.valueOf(root.val), result);
    return result;
}

private void dfs(TreeNode node, String path, List<String> result) {
    // Leaf node: add path
    if (node.left == null && node.right == null) {
        result.add(path);
        return;
    }
    
    // Recurse on left subtree
    if (node.left != null) {
        dfs(node.left, path + "->" + node.left.val, result);
    }
    
    // Recurse on right subtree
    if (node.right != null) {
        dfs(node.right, path + "->" + node.right.val, result);
    }
}

3. Validate Binary Search Tree (LC 98)

// DFS + Range Check
public boolean isValidBST(TreeNode root) {
    return dfs(root, null, null);
}

private boolean dfs(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;
    
    // Check if current node is within valid range
    if ((min != null && node.val <= min) || 
        (max != null && node.val >= max)) {
        return false;
    }
    
    // Left subtree: upper bound is current node value
    // Right subtree: lower bound is current node value
    return dfs(node.left, min, node.val) && 
           dfs(node.right, node.val, max);
}

Interview Tips and Common Mistakes

Common Mistakes

❌ Mistake 1: Missing Termination Condition

// Wrong: Will cause NullPointerException
public int maxDepth(TreeNode root) {
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Correct
public int maxDepth(TreeNode root) {
    if (root == null) return 0;  // ✓ Termination condition
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

❌ Mistake 2: Wrong Stack Order in Iteration

// Wrong: Causes BFS order
stack.push(node.left);   // Left pushed first
stack.push(node.right);  // Right pushed last -> right pops first (BFS)

// Correct: Maintains DFS order
stack.push(node.right);  // Right pushed first
stack.push(node.left);   // Left pushed last -> left pops first (DFS)

❌ Mistake 3: Forgetting to Restore State in Backtracking

// Wrong: Modified state but didn't restore
void dfs(TreeNode node, List<Integer> path) {
    path.add(node.val);
    dfs(node.left, path);   // path was modified
    dfs(node.right, path);  // left subtree results affect right subtree
}

// Correct: Restore state
void dfs(TreeNode node, List<Integer> path) {
    path.add(node.val);
    dfs(node.left, path);
    dfs(node.right, path);
    path.remove(path.size() - 1);  // ✓ Backtrack: remove current node
}

Interview Communication Tips

1. Clarify Problem Type:

   • “This requires traversing the entire tree, so I’ll use DFS…”
   • “We need to find a path, DFS is more suitable than BFS…”

2. Explain Time & Space Complexity:

   • “Recursion has space complexity O(h), which is O(log n) for balanced trees”
   • “If we’re worried about stack overflow, I can convert to iterative…”

3. Discuss Optimization Directions:

   • “To optimize space, we could use Morris traversal…”
   • “For many queries, we could cache results…”

Edge Case Checklist

✅ Always consider in interviews:

• Empty tree (root == null)
• Single node tree
• Completely unbalanced tree (chain)
• Negative target value (path sum problems)
• Negative node values

When NOT to Use DFS?

Although DFS is powerful, some scenarios favor other algorithms:

Scenario	Why Not DFS	Recommended Algorithm
Find Shortest Path	DFS doesn’t guarantee shortest	BFS
Level-Order Traversal	DFS can’t visit by level	BFS + Queue
Bipartite Graph	Need level-by-level coloring	BFS
Tree Width	Need to count by level	BFS

Time & Space Complexity Summary

Implementation	Time Complexity	Space Complexity	Notes
Recursive DFS	$O(n)$	$O(h)$	h is tree height, worst $O(n)$
Iterative DFS (Stack)	$O(n)$	$O(h)$	Explicit stack, same as recursion
Morris DFS	$O(n)$	$O(1)$	Modifies tree structure, needs restoration

Where $n$ is total nodes, $h$ is tree height:

• Balanced tree: $h = O(\log n)$
• Worst case (chain): $h = O(n)$

Summary: DFS Core Takeaways

Must-Remember Template

// Recursive DFS Universal Template
void dfs(TreeNode node) {
    if (node == null) return;       // 1. Termination condition
    
    process(node);                  // 2. Process current node
    
    dfs(node.left);                 // 3. Recurse on left subtree
    dfs(node.right);                // 4. Recurse on right subtree
    
    cleanup(node);                  // 5. Backtrack (optional)
}

Three Major DFS Use Cases

1. Tree Traversal & Property Calculation

   • Preorder/Inorder/Postorder traversal
   • Depth, node count, path sum

2. Path Problems

   • Path sum, all paths
   • Longest path, path existence

3. Tree Structure Validation

   • Symmetry, same tree, subtree
   • BST validation, balanced tree

DFS Problem-Solving Steps in Interviews

1. Identify Problem Type: Does it require traversing the entire tree?
2. Choose Recursive or Iterative: Recursive first (concise), iterative if stack overflow risk
3. Write Three Recursion Essentials: Termination, processing logic, recursive calls
4. Consider Edge Cases: Empty tree, single node, extreme cases
5. Analyze Complexity: Time $O(n)$, Space $O(h)$

Final Advice

• ✅ Practice More: Master at least 20+ classic DFS problems
• ✅ Draw Diagrams: Understand recursion tree, stack changes
• ✅ Compare with BFS: Understand when to use each
• ✅ Memorize Templates: Remember universal template for quick application

Remember: The essence of DFS is “explore deep, backtrack when stuck”. Master this mindset, and you’ll have the core weapon for solving tree and graph problems!

Happy Coding! 🚀