What is Depth-first search (DFS)?

AlgorithmsJunior~3 min read

Short answer

Depth-first search (DFS) is an algorithm for traversing graphs and trees that goes as deep as possible along one direction while there are unvisited vertices, then backtracks and continues along the nearest alternative branch. It uses a stack, either implicit (recursion) or explicit. Time complexity is O(V + E), and memory is O(V), accounting for the call stack.

Detailed explanation

The idea behind the algorithm

Start at a starting vertex s, mark it as visited.
Move to the first unvisited neighbor and repeat the process, going as deep as possible.
If the current vertex has no unvisited neighbors, backtrack to the previous vertex and look for an alternative branch.
Repeat until the stack is empty and all reachable vertices have been processed.

Recursive vs iterative variant

Recursive: simpler to write and read; the call stack acts as the traversal stack.
Iterative: an explicit stack (an array/Stack structure). Gives better control over depth and avoids call-stack overflow.
The visit order depends on the order of the neighbors and how you push them onto the stack.

Tree traversal orders

Preorder (NLR): the node first, then the left subtree, then the right.
Inorder (LNR): left, node, right (important for a BST, it gives a sorted order).
Postorder (LRN): left, right, node (used for deleting/freeing resources).

Complexity

Time: O(V + E), where V is the number of vertices and E is the number of edges.
Memory: O(V) for visited plus O(H) for the stack depth (H ≤ V). O(V) in the worst case.

Where it's used

Checking reachability and finding a path between vertices.
Finding connected components (in undirected graphs).
Cycle detection (especially in directed graphs, via colors/the recursion stack).
Topological sorting (DAG), using a postorder.
Backtracking problems: generating combinations/permutations, Sudoku, N-Queens.
Traversing a grid/maze (for example, counting "islands").

Pitfalls and tips

Don't forget visited: without it you'll get an infinite loop when cycles exist.
Deep recursion can overflow the stack: choose the iterative variant or raise the limit if possible.
Neighbor order affects the specific visit order, but not the correctness of results for classes of problems (for example, reachability/components).
To visit all vertices in a disconnected graph, run DFS starting from each unvisited vertex.

How to answer in an interview

Give a definition: "goes as deep as possible, then backtracks; uses a stack/recursion."
State the complexity: time O(V+E), memory O(V).
Mention visited and handling cycles, and the recursive and iterative variants.
Give 1-2 applications: topological sorting, reachability checks, islands on a grid.

Code examples

DFS on a graph (recursive)

javascript

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

function dfsRecursive(graph, start, visit = () => {}) {
  const visited = new Set();
  function dfs(v) {
    visited.add(v);
    visit(v);
    for (const nei of graph[v] || []) {
      if (!visited.has(nei)) dfs(nei);
    }
  }
  dfs(start);
  return visited; // the set of visited vertices
}

dfsRecursive(graph, 'A', v => console.log('visit', v));

DFS on a graph (iterative, with a stack)

javascript

function dfsIterative(graph, start, visit = () => {}) {
  const visited = new Set();
  const stack = [start];
  while (stack.length) {
    const v = stack.pop();
    if (visited.has(v)) continue;
    visited.add(v);
    visit(v);
    const neighbors = graph[v] || [];
    // To match recursion's order, push neighbors onto the stack in reverse
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const nei = neighbors[i];
      if (!visited.has(nei)) stack.push(nei);
    }
  }
  return visited;
}

// Usage example:
// dfsIterative(graph, 'A', v => console.log('visit', v));

Finding a path between two vertices (DFS)

javascript

function dfsPath(graph, start, target) {
  const visited = new Set();
  const parent = new Map();
  let found = false;

  function dfs(v) {
    if (found) return;
    visited.add(v);
    if (v === target) { found = true; return; }
    for (const nei of graph[v] || []) {
      if (!visited.has(nei)) {
        parent.set(nei, v);
        dfs(nei);
      }
    }
  }

  dfs(start);
  if (!found) return null;
  const path = [];
  for (let v = target; v != null; v = parent.get(v)) path.push(v);
  path.reverse();
  return path;
}

console.log(dfsPath(graph, 'A', 'F')); // For example: [ 'A', 'B', 'E', 'F' ]

DFS on a tree: preorder / inorder / postorder

javascript

class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new Node(1,
  new Node(2, new Node(4), new Node(5)),
  new Node(3)
);

function preorder(node, visit) {
  if (!node) return;
  visit(node.val);
  preorder(node.left, visit);
  preorder(node.right, visit);
}

function inorder(node, visit) {
  if (!node) return;
  inorder(node.left, visit);
  visit(node.val);
  inorder(node.right, visit);
}

function postorder(node, visit) {
  if (!node) return;
  postorder(node.left, visit);
  postorder(node.right, visit);
  visit(node.val);
}

preorder(root, v => console.log('pre', v));   // 1,2,4,5,3
inorder(root, v => console.log('in', v));     // 4,2,5,1,3
postorder(root, v => console.log('post', v)); // 4,5,2,3,1

DFS on a grid (counting the number of "islands")

javascript

function numIslands(grid) {
  const m = grid.length;
  const n = grid[0]?.length || 0;
  const seen = Array.from({ length: m }, () => Array(n).fill(false));
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];

  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= m || c >= n) return;
    if (seen[r][c] || grid[r][c] !== '1') return;
    seen[r][c] = true;
    for (const [dr, dc] of dirs) dfs(r + dr, c + dc);
  }

  let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (!seen[r][c] && grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }
  return count;
}

const grid = [
  ['1','1','0','0'],
  ['1','0','0','1'],
  ['0','0','1','1'],
];
console.log(numIslands(grid)); // 3

Cycle detection and topological sorting (DAG)

javascript

function hasCycleDirected(graph) {
  const color = new Map(); // 0=white,1=gray,2=black
  const nodes = Object.keys(graph);

  function dfs(v) {
    color.set(v, 1);
    for (const nei of graph[v] || []) {
      const c = color.get(nei) || 0;
      if (c === 1) return true; // back edge => cycle
      if (c === 0 && dfs(nei)) return true;
    }
    color.set(v, 2);
    return false;
  }

  for (const v of nodes) {
    if ((color.get(v) || 0) === 0 && dfs(v)) return true;
  }
  return false;
}

function topoSort(graph) {
  const visited = new Set();
  const order = [];

  function dfs(v) {
    visited.add(v);
    for (const nei of graph[v] || []) {
      if (!visited.has(nei)) dfs(nei);
    }
    order.push(v); // postorder
  }

  for (const v of Object.keys(graph)) {
    if (!visited.has(v)) dfs(v);
  }
  order.reverse();
  return order;
}

// Example:
const dag = {
  A: ['C'],
  B: ['C', 'D'],
  C: ['E'],
  D: ['F'],
  E: ['H', 'F'],
  F: ['G'],
  G: [],
  H: []
};

console.log('hasCycle', hasCycleDirected(dag)); // false
console.log('topo', topoSort(dag)); // one of the valid orders

Summary

DFS is a simple and powerful fundamental algorithm. It traverses a graph/tree by going as deep as possible, relies on a stack (explicit or recursive), has linear complexity O(V+E), and is widely used: from path finding and components to topological sorting and backtracking problems. The key points: correctly maintain visited and account for stack depth.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.