Leetcode/Guide/DFS

Contents

Depth-First Search (DFS) is a fundamental algorithm for exploring trees and graphs.
Unlike BFS (which explores level by level), DFS explores as deep as possible along each branch before backtracking.

DFS can be implemented using recursion (implicit stack) or an explicit stack (iterative).

---

🧠 Core Idea

• Start from a source node.
• Explore one path completely before moving to another.
• Use:
  • A stack (or recursion) to remember where you came from.
  • A visited set to avoid infinite loops (especially in graphs).

DFS is great for:

• Searching or detecting paths
• Tree traversal (preorder, inorder, postorder)
• Cycle detection
• Backtracking (like solving mazes, generating combinations, etc.)

---

Example 1 — DFS Traversal (Tree, Recursive)

function dfsTreeRecursive(node) {
  if (!node) return [];

  const result = [];

  function traverse(currentNode) {
    result.push(currentNode.value);
    if (currentNode.left) traverse(currentNode.left);
    if (currentNode.right) traverse(currentNode.right);
  }

  traverse(node);
  return result;
}

// Demo
const tree = {
  value: 1,
  left: { value: 2, left: { value: 4 }, right: { value: 5 } },
  right: { value: 3, left: { value: 6 }, right: { value: 7 } }
};

console.log(dfsTreeRecursive(tree));
// Output: [1, 2, 4, 5, 3, 6, 7] (Preorder traversal)

✅ Why this works:
The recursive calls naturally go deep into each subtree before returning — exactly what DFS means.

---

Example 2 — DFS Traversal (Tree, Iterative with Stack)

You can do the same without recursion using an explicit stack.

function dfsTreeIterative(rootNode) {
  if (!rootNode) return [];

  const stack = [rootNode];
  const result = [];

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

    // Push right first so left is processed first
    if (currentNode.right) stack.push(currentNode.right);
    if (currentNode.left) stack.push(currentNode.left);
  }

  return result;
}

// Demo
console.log(dfsTreeIterative(tree));
// Output: [1, 2, 4, 5, 3, 6, 7]

✅ Why this works:
The stack preserves the nodes to return to later, mimicking recursion manually.

---

Example 3 — DFS on a Graph (Recursive)

function dfsGraphRecursive(graph, startNode, visited = new Set()) {
  visited.add(startNode);
  const result = [startNode];

  const neighbors = graph[startNode] || [];
  for (const neighbor of neighbors) {
    if (!visited.has(neighbor)) {
      result.push(...dfsGraphRecursive(graph, neighbor, visited));
    }
  }

  return result;
}

// Demo
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

console.log(dfsGraphRecursive(graph, 'A'));
// Output: ['A', 'B', 'D', 'E', 'F', 'C']

✅ Why this works:
The recursion keeps diving into new nodes until no unvisited neighbors remain, then unwinds (backtracks).

---

Example 4 — DFS on a Graph (Iterative with Stack)

function dfsGraphIterative(graph, startNode) {
  const stack = [startNode];
  const visited = new Set();
  const result = [];

  while (stack.length > 0) {
    const currentNode = stack.pop();

    if (!visited.has(currentNode)) {
      visited.add(currentNode);
      result.push(currentNode);

      const neighbors = graph[currentNode] || [];
      // Push neighbors in reverse order to maintain consistent order
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const neighbor = neighbors[i];
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }

  return result;
}

// Demo
console.log(dfsGraphIterative(graph, 'A'));
// Output: ['A', 'B', 'D', 'E', 'F', 'C']

✅ Why this works:
Just like recursion, the stack drives the depth-first behavior — but explicitly.

---

Example 5 — DFS in a Grid (Backtracking)

DFS with backtracking is often used to explore all possible paths — for example, finding all paths in a maze.

function dfsGridWithBacktracking(matrix, startRow, startCol, visited, path = [], allPaths = []) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;

  const isInBounds = startRow >= 0 && startRow < numRows && startCol >= 0 && startCol < numCols;
  if (!isInBounds || matrix[startRow][startCol] === 0 || visited[startRow][startCol]) return;

  visited[startRow][startCol] = true;
  path.push([startRow, startCol]);

  // Example goal: bottom-right corner
  if (startRow === numRows - 1 && startCol === numCols - 1) {
    allPaths.push([...path]);
  } else {
    dfsGridWithBacktracking(matrix, startRow + 1, startCol, visited, path, allPaths);
    dfsGridWithBacktracking(matrix, startRow - 1, startCol, visited, path, allPaths);
    dfsGridWithBacktracking(matrix, startRow, startCol + 1, visited, path, allPaths);
    dfsGridWithBacktracking(matrix, startRow, startCol - 1, visited, path, allPaths);
  }

  // Backtrack
  path.pop();
  visited[startRow][startCol] = false;

  return allPaths;
}

// Demo
const grid = [
  [1, 1, 0],
  [1, 1, 1],
  [0, 1, 1]
];
const visited = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(false));
console.log(dfsGridWithBacktracking(grid, 0, 0, visited));
// Possible output: all valid paths from (0,0) to (2,2)

✅ Why this works:
We mark cells as visited when exploring, and unmark them (backtrack) when returning, ensuring we explore all valid paths.

---

Example 6 — DFS in a Grid (Without Backtracking)

This version simply visits all reachable cells — no path tracking needed.

function dfsGridWithoutBacktracking(matrix, startRow, startCol, visited) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;

  const isInBounds = startRow >= 0 && startRow < numRows && startCol >= 0 && startCol < numCols;
  if (!isInBounds || matrix[startRow][startCol] === 0 || visited[startRow][startCol]) return;

  visited[startRow][startCol] = true;
  console.log(`Visited: (${startRow}, ${startCol})`);

  dfsGridWithoutBacktracking(matrix, startRow + 1, startCol, visited);
  dfsGridWithoutBacktracking(matrix, startRow - 1, startCol, visited);
  dfsGridWithoutBacktracking(matrix, startRow, startCol + 1, visited);
  dfsGridWithoutBacktracking(matrix, startRow, startCol - 1, visited);
}

// Demo
const simpleGrid = [
  [1, 1, 0],
  [1, 1, 1],
  [0, 1, 1]
];
const visitedCells = Array.from({ length: simpleGrid.length }, () => Array(simpleGrid[0].length).fill(false));
dfsGridWithoutBacktracking(simpleGrid, 0, 0, visitedCells);

✅ Why this works:
DFS explores all connected cells deeply before moving sideways — suitable for island counting, region detection, etc.

---

🧩 Summary Table

---

🚀 Key Takeaways

• DFS = Go deep first, using recursion or stack.
• Perfect for pathfinding, searching, and structure analysis.
• Backtracking is optional — use it when exploring all possible paths.
• Time complexity: O(V + E) (V = vertices, E = edges)
• Space complexity: O(V) (due to stack or recursion)

Mastering DFS and backtracking opens the door to solving problems like:

• Mazes and island counts
• Sudoku and permutations
• Graph traversal and connectivity
• Recursive exploration of trees and grids