DSA · Patterns, not puzzles

How does depth-first search work?

MediumdfsgraphsrecursionUpdated Oct 2026

Short answer

Depth-first search follows one path as far as possible before backtracking, using recursion or an explicit stack. It is O(V + E) and is used for connectivity, cycle detection and topological ordering.

DFS is the natural graph traversal when you care about reachability or structure rather than shortest distance. It commits to a path, explores it fully, then returns to try the next branch. The visited set prevents infinite loops in cyclic graphs.

function dfs(graph, start, visited = new Set(), order = []) {
  visited.add(start);
  order.push(start);
  for (const next of graph.get(start) || []) {
    if (!visited.has(next)) dfs(graph, next, visited, order);
  }
  return order;
}

The visited set is shared across recursive calls, so each node is processed once.

Recursive versus iterative

Recursive DFS is shorter and matches the mental model
Recursive DFS can overflow the call stack on deep graphs
Iterative DFS uses an explicit stack and avoids that limit
The order of neighbours affects the traversal order but not correctness
For cycle detection, track the current recursion path separately from fully visited nodes

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];
  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const next of graph.get(node) || []) {
      if (!visited.has(next)) stack.push(next);
    }
  }
  return order;
}

Popping from the end gives depth-first behaviour. Nodes may be pushed more than once, so the visited check happens on pop.

DFS does not find shortest paths in an unweighted graph. It finds some path, and that path may be longer than necessary. Use BFS when distance matters.

Follow-ups you should expect

Interviewers use these to check whether the first answer was understanding or memorisation.

1How do you avoid stack overflow in recursive DFS?
2How does DFS detect a cycle in a directed graph?
3Why does iterative DFS push neighbours onto a stack?
4When would you choose DFS over BFS?

Say it in the interview

DFS goes as deep as possible along one branch before backtracking. I keep a visited set and recurse into unvisited neighbours, or use an explicit stack to avoid recursion limits. It runs in O(V + E) with an adjacency list. I use it for connectivity, cycle detection and topological sort, but not for shortest paths, because it does not explore by distance.

Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.

Now say it out loud.

Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.

Start a free DSA interview Browse all questions

Recursive versus iterative

Follow-ups you should expect

Related questions

Now say it out loud.