Depth-First Search: Recursive and Iterative TypeScript Implementations of DFS

Table of Contents

Overview Problem Definition Core Principle: Step-by-Step Diagram Recursive Perspective Iterative Perspective Detailed Algorithm Steps TypeScript Implementation 1. Graph DFS Template 2. Iterative DFS 3. Binary Tree Path Sum 4. Maximum Area of an Island 5. Path Enumeration Engineering Optimization: Recursion or Explicit Stack Applications and Limitations Typical Applications Limitations Summary

865 words

4 minutes

Depth-First Search: Recursive and Iterative TypeScript Implementations of DFS

2026-04-26

Algorithms

Depth-First Search

/

DFS

/

TypeScript

/

Algorithms

Overview#

Depth-First Search (DFS) is a traversal method that goes as deep as possible along one path, then backtracks to a branching point to continue searching. It can use recursion to implicitly maintain the call stack, or an explicit stack for an iterative implementation.

Prerequisites

Stack: DFS path state is last-in, first-out

Recursion: naturally expresses deep exploration in trees, graphs, and grids

visited marking: used in graphs and grids to avoid revisiting

Problem Definition#

Given a tree, graph, or grid structure, explore all reachable states from a starting point, and compute results or determine whether a target exists during the visit process.

Element	Description
Input	Starting point, adjacency relations, grid or tree nodes
Output	Traversal order, connected regions, path results, or boolean determination
Core state	Current node, path, visited set, recursive return value
Applicable scenarios	Connectivity, path enumeration, tree recursion, backtracking search

Core Principle: Step-by-Step Diagram#

DFS prioritizes going deep into one branch until it cannot continue, then returns to the previous branching point:

Starting from node 1, the preorder DFS visit order might be:

1
1 → 2 → 4 → rollback → 5 → rollback → 3 → 6

Recursive Perspective#

Each level of recursion is responsible for only one node: process the current node, recursively process neighbors, and return subproblem results when necessary.

Iterative Perspective#

Explicitly maintain a stack, pop the top node each time, and push unvisited neighbors onto the stack.

Detailed Algorithm Steps#

1
Algorithm: DFS(node)
2
Input: current node node
3
Output: traversal or computation result
4

5
1. If node is empty or already visited, return
6
2. Mark node as visited
7
3. Process the current node
8
4. Traverse each neighbor next of node:
9
5.     DFS(next)
10
6. Merge and return based on the sub-results

Complexity Analysis:

Scenario	Time Complexity	Space Complexity	Description
Tree traversal	O(n)	O(h)	h is tree height
Graph traversal	O(V + E)	O(V)	visited and recursion stack
Grid search	O(mn)	O(mn)	each cell is visited at most once
Backtracking search	Exponential	O(depth)	depends on branching factor and depth

TypeScript Implementation#

1. Graph DFS Template#

1
function dfsGraph(graph: Map<number, number[]>, start: number): number[] {
2
  const visited = new Set<number>();
3
  const result: number[] = [];
4

5
  function dfs(node: number): void {
6
    if (visited.has(node)) return;
7
    visited.add(node);
8
    result.push(node);
9

10
    for (const next of graph.get(node) ?? []) {
11
      dfs(next);
12
    }
13
  }
14

15
  dfs(start);
16
  return result;
17
}

2. Iterative DFS#

1
function dfsIterative(graph: Map<number, number[]>, start: number): number[] {
2
  const stack = [start];
3
  const visited = new Set<number>([start]);
4
  const result: number[] = [];
5

6
  while (stack.length > 0) {
7
    const node = stack.pop()!;
8
    result.push(node);
9

10
    for (const next of graph.get(node) ?? []) {
11
      if (visited.has(next)) continue;
12
      visited.add(next);
13
      stack.push(next);
14
    }
15
  }
16

17
  return result;
18
}

3. Binary Tree Path Sum#

1
class TreeNode {
2
  val: number;
3
  left: TreeNode | null;
4
  right: TreeNode | null;
5

6
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
7
    this.val = val;
8
    this.left = left;
9
    this.right = right;
10
  }
11
}
12

13
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
14
  if (root === null) return false;
15
  if (root.left === null && root.right === null) return root.val === targetSum;
16

17
  return (
18
    hasPathSum(root.left, targetSum - root.val) ||
19
    hasPathSum(root.right, targetSum - root.val)
20
  );
21
}

4. Maximum Area of an Island#

1
function maxAreaOfIsland(grid: number[][]): number {
2
  const m = grid.length;
3
  const n = grid[0].length;
4
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
5

6
  function dfs(row: number, col: number): number {
7
    if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] !== 1) return 0;
8

9
    grid[row][col] = 0;
10
    let area = 1;
11
    for (const [dr, dc] of dirs) {
12
      area += dfs(row + dr, col + dc);
13
    }
14
    return area;
15
  }
16

17
  let maxArea = 0;
18
  for (let i = 0; i < m; i++) {
19
    for (let j = 0; j < n; j++) {
20
      if (grid[i][j] === 1) {
21
        maxArea = Math.max(maxArea, dfs(i, j));
22
      }
23
    }
24
  }
25

26
  return maxArea;
27
}

5. Path Enumeration#

1
function pathSum(root: TreeNode | null, targetSum: number): number[][] {
2
  const result: number[][] = [];
3
  const path: number[] = [];
4

5
  function dfs(node: TreeNode | null, remaining: number): void {
6
    if (node === null) return;
7

8
    path.push(node.val);
9
    if (node.left === null && node.right === null && node.val === remaining) {
10
      result.push([...path]);
11
    }
12

13
    dfs(node.left, remaining - node.val);
14
    dfs(node.right, remaining - node.val);
15
    path.pop();
16
  }
17

18
  dfs(root, targetSum);
19
  return result;
20
}

Engineering Optimization: Recursion or Explicit Stack#

Approach	Advantages	Cost
Recursive DFS	Natural expression, short code	Stack overflow possible if depth is too large
Iterative DFS	Controllable, does not depend on the call stack	Requires manually maintaining the stack and state
In-place marking	Saves visited space	Modifies the input data
visited set	Does not destroy the input	Extra O(n) space

In tree structures, recursion is usually the clearest; in graphs and large grids, if depth is uncontrollable, an explicit stack is more reliable.

Applications and Limitations#

Typical Applications#

Tree traversal, depth, height, path computation
Graph connectivity, cycle detection, topology-related determination
Grid islands, mazes, region filling
Decision tree search in backtracking problems

Limitations#

Limitation	Description
Does not guarantee shortest path	For unweighted shortest paths, BFS should be preferred
Recursion depth risk	Chain-like structures may cause the call stack to become too deep
State is easy to confuse	Path-type problems require attention to backtracking and copying

Summary#

Key Points:

DFS = go deep along one path to the end, then backtrack to explore other branches.
Tree problems commonly use recursion, while graph and grid problems must handle visited.
Path enumeration should add to the path on entry and undo on exit.
When the minimum number of steps is needed, prefer BFS over DFS.

--- END CONTENT ---