Depth-First Search (DFS)

November 19, 2025

#dfs #depth-first-search #graph-traversal #algorithms #graph #recursion #interviewing

Introduction

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. Think of it like exploring a maze by always taking the first path you see, going as deep as possible, then backtracking when you hit a dead end.

DFS is essential for detecting cycles, topological sorting, finding connected components, and solving maze/puzzle problems. Unlike BFS which uses a queue, DFS uses a stack (or recursion, which implicitly uses the call stack).

Review Graphs, Stacks, and Binary Trees first if needed.

DFS runs in O(V + E) time and is particularly useful for detecting cycles, finding paths, and problems requiring backtracking or exhaustive exploration.

How DFS works

DFS explores a graph in depth:

Start at a source vertex
Explore one neighbor completely before moving to the next
Recursively visit unvisited neighbors
Backtrack when no unvisited neighbors remain

Visual example:

Graph:
    A --- B --- E
    |     |
    C --- D

DFS from A (one possible order):
Visit A → go to B → go to E (dead end, backtrack)
       → back to B → go to D → go to C (already visited A)
       → back to D (dead end) → done

Order: A, B, E, D, C

DFS algorithm

Key components:

Stack: Maintains vertices to visit (LIFO) - or use recursion
Visited set: Tracks visited vertices to avoid cycles
Backtracking: Return to previous vertex when stuck

Steps:

Mark starting vertex as visited
For each unvisited neighbor:
- Recursively visit that neighbor
Backtrack when all neighbors are visited

DFS implementation

Recursive DFS on a graph

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }

  // DFS recursive
  dfs(start) {
    const visited = new Set();
    const result = [];

    const dfsHelper = (vertex) => {
      visited.add(vertex);
      result.push(vertex);

      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          dfsHelper(neighbor);
        }
      }
    };

    dfsHelper(start);
    return result;
  }

  // DFS with pre and post order tracking
  dfsWithTiming(start) {
    const visited = new Set();
    const preOrder = [];
    const postOrder = [];

    const dfsHelper = (vertex) => {
      visited.add(vertex);
      preOrder.push(vertex); // Visit on the way down

      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          dfsHelper(neighbor);
        }
      }

      postOrder.push(vertex); // Visit on the way up (backtracking)
    };

    dfsHelper(start);
    return { preOrder, postOrder };
  }
}

// Example usage
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'D');

console.log(graph.dfs('A'));  // ['A', 'B', 'D', 'E', 'C']
console.log(graph.dfsWithTiming('A'));
// { preOrder: ['A', 'B', 'D', 'E', 'C'],
//   postOrder: ['D', 'E', 'B', 'C', 'A'] }

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.adjacency_list[v1].append(v2)
        self.adjacency_list[v2].append(v1)

    def dfs(self, start):
        """DFS recursive"""
        visited = set()
        result = []

        def dfs_helper(vertex):
            visited.add(vertex)
            result.append(vertex)

            for neighbor in self.adjacency_list.get(vertex, []):
                if neighbor not in visited:
                    dfs_helper(neighbor)

        dfs_helper(start)
        return result

    def dfs_with_timing(self, start):
        """DFS with pre and post order tracking"""
        visited = set()
        pre_order = []
        post_order = []

        def dfs_helper(vertex):
            visited.add(vertex)
            pre_order.append(vertex)  # Visit on the way down

            for neighbor in self.adjacency_list.get(vertex, []):
                if neighbor not in visited:
                    dfs_helper(neighbor)

            post_order.append(vertex)  # Visit on the way up

        dfs_helper(start)
        return {'preOrder': pre_order, 'postOrder': post_order}

# Example usage
graph = Graph()
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'D')

print(graph.dfs('A'))  # ['A', 'B', 'D', 'E', 'C']
print(graph.dfs_with_timing('A'))
# {'preOrder': ['A', 'B', 'D', 'E', 'C'],
#  'postOrder': ['D', 'E', 'B', 'C', 'A']}

import java.util.*;

public class Graph {
    private Map<String, List<String>> adjacencyList;

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

    public void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String v1, String v2) {
        addVertex(v1);
        addVertex(v2);
        adjacencyList.get(v1).add(v2);
        adjacencyList.get(v2).add(v1);
    }

    // DFS recursive
    public List<String> dfs(String start) {
        Set<String> visited = new HashSet<>();
        List<String> result = new ArrayList<>();
        dfsHelper(start, visited, result);
        return result;
    }

    private void dfsHelper(String vertex, Set<String> visited,
                          List<String> result) {
        visited.add(vertex);
        result.add(vertex);

        for (String neighbor : adjacencyList.getOrDefault(vertex,
                                new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited, result);
            }
        }
    }

    // DFS with pre and post order
    public Map<String, List<String>> dfsWithTiming(String start) {
        Set<String> visited = new HashSet<>();
        List<String> preOrder = new ArrayList<>();
        List<String> postOrder = new ArrayList<>();

        dfsTimingHelper(start, visited, preOrder, postOrder);

        Map<String, List<String>> result = new HashMap<>();
        result.put("preOrder", preOrder);
        result.put("postOrder", postOrder);
        return result;
    }

    private void dfsTimingHelper(String vertex, Set<String> visited,
                                 List<String> preOrder,
                                 List<String> postOrder) {
        visited.add(vertex);
        preOrder.add(vertex);

        for (String neighbor : adjacencyList.getOrDefault(vertex,
                                new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsTimingHelper(neighbor, visited, preOrder, postOrder);
            }
        }

        postOrder.add(vertex);
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "C");
        graph.addEdge("B", "D");
        graph.addEdge("B", "E");
        graph.addEdge("C", "D");

        System.out.println(graph.dfs("A"));
        // [A, B, D, E, C]
        System.out.println(graph.dfsWithTiming("A"));
        // {preOrder=[A, B, D, E, C], postOrder=[D, E, B, C, A]}
    }
}

Iterative DFS using stack

class Graph {
  // ... previous code

  dfsIterative(start) {
    const visited = new Set();
    const stack = [start];
    const result = [];

    visited.add(start);

    while (stack.length > 0) {
      const vertex = stack.pop();
      result.push(vertex);

      // Add neighbors in reverse order to match recursive DFS order
      const neighbors = this.adjacencyList.get(vertex) || [];
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const neighbor = neighbors[i];
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          stack.push(neighbor);
        }
      }
    }

    return result;
  }
}

console.log(graph.dfsIterative('A'));  // ['A', 'B', 'D', 'E', 'C']

class Graph:
    # ... previous code

    def dfs_iterative(self, start):
        visited = set()
        stack = [start]
        result = []

        visited.add(start)

        while stack:
            vertex = stack.pop()
            result.append(vertex)

            # Add neighbors in reverse to match recursive order
            neighbors = self.adjacency_list.get(vertex, [])
            for neighbor in reversed(neighbors):
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)

        return result

print(graph.dfs_iterative('A'))  # ['A', 'B', 'D', 'E', 'C']

public List<String> dfsIterative(String start) {
    Set<String> visited = new HashSet<>();
    Stack<String> stack = new Stack<>();
    List<String> result = new ArrayList<>();

    visited.add(start);
    stack.push(start);

    while (!stack.isEmpty()) {
        String vertex = stack.pop();
        result.add(vertex);

        List<String> neighbors = adjacencyList.getOrDefault(vertex,
                                  new ArrayList<>());
        // Add in reverse order to match recursive DFS
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            String neighbor = neighbors.get(i);
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                stack.push(neighbor);
            }
        }
    }

    return result;
}

DFS on a binary tree

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Pre-order DFS (Root, Left, Right)
function dfsPreOrder(root, result = []) {
  if (root === null) return result;
  result.push(root.value);
  dfsPreOrder(root.left, result);
  dfsPreOrder(root.right, result);
  return result;
}

// In-order DFS (Left, Root, Right)
function dfsInOrder(root, result = []) {
  if (root === null) return result;
  dfsInOrder(root.left, result);
  result.push(root.value);
  dfsInOrder(root.right, result);
  return result;
}

// Post-order DFS (Left, Right, Root)
function dfsPostOrder(root, result = []) {
  if (root === null) return result;
  dfsPostOrder(root.left, result);
  dfsPostOrder(root.right, result);
  result.push(root.value);
  return result;
}

// Example
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(dfsPreOrder(root));   // [1, 2, 4, 5, 3]
console.log(dfsInOrder(root));    // [4, 2, 5, 1, 3]
console.log(dfsPostOrder(root));  // [4, 5, 2, 3, 1]

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def dfs_pre_order(root, result=None):
    """Pre-order DFS (Root, Left, Right)"""
    if result is None:
        result = []
    if root is None:
        return result
    result.append(root.value)
    dfs_pre_order(root.left, result)
    dfs_pre_order(root.right, result)
    return result

def dfs_in_order(root, result=None):
    """In-order DFS (Left, Root, Right)"""
    if result is None:
        result = []
    if root is None:
        return result
    dfs_in_order(root.left, result)
    result.append(root.value)
    dfs_in_order(root.right, result)
    return result

def dfs_post_order(root, result=None):
    """Post-order DFS (Left, Right, Root)"""
    if result is None:
        result = []
    if root is None:
        return result
    dfs_post_order(root.left, result)
    dfs_post_order(root.right, result)
    result.append(root.value)
    return result

# Example
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(dfs_pre_order(root))    # [1, 2, 4, 5, 3]
print(dfs_in_order(root))     # [4, 2, 5, 1, 3]
print(dfs_post_order(root))   # [4, 5, 2, 3, 1]

class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int value) { this.value = value; }
}

public class DFSTree {
    // Pre-order DFS (Root, Left, Right)
    public static void dfsPreOrder(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.value);
        dfsPreOrder(root.left, result);
        dfsPreOrder(root.right, result);
    }

    // In-order DFS (Left, Root, Right)
    public static void dfsInOrder(TreeNode root, List<Integer> result) {
        if (root == null) return;
        dfsInOrder(root.left, result);
        result.add(root.value);
        dfsInOrder(root.right, result);
    }

    // Post-order DFS (Left, Right, Root)
    public static void dfsPostOrder(TreeNode root, List<Integer> result) {
        if (root == null) return;
        dfsPostOrder(root.left, result);
        dfsPostOrder(root.right, result);
        result.add(root.value);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        List<Integer> pre = new ArrayList<>();
        dfsPreOrder(root, pre);
        System.out.println(pre);  // [1, 2, 4, 5, 3]

        List<Integer> in = new ArrayList<>();
        dfsInOrder(root, in);
        System.out.println(in);   // [4, 2, 5, 1, 3]

        List<Integer> post = new ArrayList<>();
        dfsPostOrder(root, post);
        System.out.println(post); // [4, 5, 2, 3, 1]
    }
}

Common DFS problems

1. Detect cycle in undirected graph

function hasCycle(graph) {
  const visited = new Set();

  function dfs(vertex, parent) {
    visited.add(vertex);

    for (const neighbor of graph.adjacencyList.get(vertex) || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, vertex)) return true;
      } else if (neighbor !== parent) {
        // Visited neighbor that's not parent = cycle!
        return true;
      }
    }

    return false;
  }

  // Check all components
  for (const vertex of graph.adjacencyList.keys()) {
    if (!visited.has(vertex)) {
      if (dfs(vertex, null)) return true;
    }
  }

  return false;
}

def has_cycle(graph):
    visited = set()

    def dfs(vertex, parent):
        visited.add(vertex)

        for neighbor in graph.adjacency_list.get(vertex, []):
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif neighbor != parent:
                # Visited neighbor that's not parent = cycle!
                return True

        return False

    # Check all components
    for vertex in graph.adjacency_list.keys():
        if vertex not in visited:
            if dfs(vertex, None):
                return True

    return False

public static boolean hasCycle(Graph graph) {
    Set<String> visited = new HashSet<>();

    for (String vertex : graph.adjacencyList.keySet()) {
        if (!visited.contains(vertex)) {
            if (dfs(vertex, null, visited, graph)) {
                return true;
            }
        }
    }

    return false;
}

private static boolean dfs(String vertex, String parent,
                          Set<String> visited, Graph graph) {
    visited.add(vertex);

    for (String neighbor : graph.getNeighbors(vertex)) {
        if (!visited.contains(neighbor)) {
            if (dfs(neighbor, vertex, visited, graph)) {
                return true;
            }
        } else if (!neighbor.equals(parent)) {
            return true; // Cycle found
        }
    }

    return false;
}

2. Find all paths from source to target

function allPaths(graph, start, end) {
  const paths = [];

  function dfs(vertex, path) {
    path.push(vertex);

    if (vertex === end) {
      paths.push([...path]); // Save a copy
    } else {
      for (const neighbor of graph.adjacencyList.get(vertex) || []) {
        if (!path.includes(neighbor)) { // Avoid cycles in path
          dfs(neighbor, path);
        }
      }
    }

    path.pop(); // Backtrack
  }

  dfs(start, []);
  return paths;
}

console.log(allPaths(graph, 'A', 'D'));
// [['A', 'B', 'D'], ['A', 'C', 'D']]

def all_paths(graph, start, end):
    paths = []

    def dfs(vertex, path):
        path.append(vertex)

        if vertex == end:
            paths.append(path[:])  # Save a copy
        else:
            for neighbor in graph.adjacency_list.get(vertex, []):
                if neighbor not in path:  # Avoid cycles
                    dfs(neighbor, path)

        path.pop()  # Backtrack

    dfs(start, [])
    return paths

print(all_paths(graph, 'A', 'D'))
# [['A', 'B', 'D'], ['A', 'C', 'D']]

public static List<List<String>> allPaths(Graph graph,
                                          String start, String end) {
    List<List<String>> paths = new ArrayList<>();
    List<String> path = new ArrayList<>();
    dfsAllPaths(start, end, path, paths, graph);
    return paths;
}

private static void dfsAllPaths(String vertex, String end,
                                List<String> path,
                                List<List<String>> paths,
                                Graph graph) {
    path.add(vertex);

    if (vertex.equals(end)) {
        paths.add(new ArrayList<>(path));
    } else {
        for (String neighbor : graph.getNeighbors(vertex)) {
            if (!path.contains(neighbor)) {
                dfsAllPaths(neighbor, end, path, paths, graph);
            }
        }
    }

    path.remove(path.size() - 1); // Backtrack
}

3. Topological sort (directed acyclic graph)

function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(vertex) {
    visited.add(vertex);

    for (const neighbor of graph.adjacencyList.get(vertex) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }

    stack.push(vertex); // Add to stack on the way back up
  }

  // Visit all vertices
  for (const vertex of graph.adjacencyList.keys()) {
    if (!visited.has(vertex)) {
      dfs(vertex);
    }
  }

  return stack.reverse(); // Reverse to get topological order
}

DFS vs BFS comparison

Feature	DFS	BFS
Data structure	Stack/Recursion (LIFO)	Queue (FIFO)
Order	Depth first	Level by level
Shortest path	❌ No	✅ Yes (unweighted)
Space	O(height)	O(width)
Use cases	Cycle detection, topological sort, pathfinding	Shortest path, level-order
Backtracking	✅ Natural	❌ Not typical

Complexity analysis

Time: O(V + E) where V = vertices, E = edges
Space:
- Recursive: O(V) for call stack + visited set
- Iterative: O(V) for explicit stack + visited set

Common pitfalls

Stack overflow: Deep recursion on large graphs
Not marking visited: Leads to infinite loops
Forgetting to backtrack: In path-finding problems
Confusing pre/post order: Know when to process vertices
Not handling disconnected components: May miss vertices

When to use DFS

Detecting cycles in graphs
Topological sorting of directed acyclic graphs
Finding connected components
Pathfinding with backtracking
Solving mazes and puzzles
Tree traversals (in-order, pre-order, post-order)
Generating permutations/combinations

Practice problems

Clone a graph (DFS)
Number of islands (2D grid DFS)
Course schedule (detect cycle with DFS)
Surrounded regions (capture regions on board)
Pacific Atlantic water flow
Longest increasing path in matrix
Word search (backtracking with DFS)
Validate binary search tree
Path sum in binary tree
Serialize and deserialize binary tree
All paths from source to target
Keys and rooms
Reconstruct itinerary
Employee importance (DFS on graph)
Lowest common ancestor in binary tree

Complexity summary

Time: O(V + E) — visit each vertex and edge once
Space: O(V) — visited set and recursion stack/explicit stack

DFS is essential for graph problems requiring deep exploration, cycle detection, and backtracking. Master both DFS and BFS to handle the full range of graph and tree traversal problems.

Table of Contents