Solution

You'll write a traversal that, given an adjacency map and a start node, walks the graph one branch all the way down before backing up to try the next branch — the canonical depth-first visit order.

The problem, in plain English

You're handed a graph (a bunch of nodes with directed arrows between them) and a node to start from. Your job is to list every node reachable from the start, in the order you would see them if you committed to one path, walked it to the end, then backed up to the last unexplored fork and committed to that one. It's the same shape problem as breadth-first search, but the visit order is different: BFS sweeps level by level; DFS dives.

The graph is stored as an adjacency map — a plain object whose keys are node names and whose values are arrays of the names that node points to. That's a common minimal representation and lets us write the traversal without a separate Graph class.

The mental model

Think of yourself as someone exploring a cave system. At every fork you pick the leftmost passage, go in, and keep picking the leftmost passage until you hit a dead end. Then you back up one fork and try the next passage from there. You keep a notebook of rooms you've already been in so you never re-enter one — that's what makes DFS terminate even when the cave has loops.

The reason DFS is naturally recursive is that "explore the graph from node X" is the same kind of problem as "explore the graph from one of X's neighbors" — just smaller. Each recursive call peels off one node, marks it visited, and delegates to its children.

A first attempt

If you've seen BFS recently you might reach for a queue, swap it for a stack, and call it done:

function depthFirstSearch(graph, start) {
  const result = [];
  const stack = [start];
  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node);                  // record on pop
    for (const next of graph[node]) {   // push every neighbor
      stack.push(next);
    }
  }
  return result;
}

Two things go wrong on the first interesting input. It loops forever on any cycle — A: ['B'], B: ['A'] keeps re-pushing A and B until the stack overflows. The visit order is also subtly wrong: because pop() returns the last item pushed, the neighbors come out in reverse adjacency order. On A: ['B', 'C'] we push B then C, then pop C first — so we walk C's whole subtree before touching B, which contradicts the spec ("neighbors visited in order they appear").

Both problems have the same root cause: the naive version doesn't remember which nodes it has already processed.

The working solution

The simplest fix is to switch to recursion, keep a visited set, and skip any neighbor that's already in it. Recursion naturally handles the adjacency-order issue too: we iterate neighbors left-to-right and recurse into each one before moving on.

function depthFirstSearch(graph, start) {
  // Spec edge case: if `start` isn't a key in `graph`, there's nothing
  // reachable and the result is empty. `hasOwnProperty` (called via the
  // prototype to dodge any user-defined "hasOwnProperty" key on the map)
  // is more honest than `graph[start] !== undefined`, which would mistakenly
  // accept inherited keys.
  if (!Object.prototype.hasOwnProperty.call(graph, start)) return [];

  const result = [];
  const visited = new Set(); // O(1) "have we been here?" lookup; matters once cycles enter.

  function visit(node) {
    // Cycle / shared-node guard. Without this, A -> B -> A would recurse
    // into A again and either loop forever (no guard) or grow the result
    // past one entry per node.
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node); // pre-order: record on entry, before recursing into children.

    // `graph[node] || []` defends against a neighbor that appears in some
    // node's adjacency list but isn't itself a key in `graph`. Real-world
    // graphs sometimes have this kind of dangling reference; we just
    // record the node and stop, rather than crashing on `undefined.length`.
    const neighbors = graph[node] || [];
    for (let i = 0; i < neighbors.length; i++) {
      // Recurse into each neighbor IN ORDER, fully exploring its subtree
      // before moving on to the next sibling. That's what makes this DFS
      // rather than BFS, and what gives us [A, B, D, E, C, F, G] rather
      // than the BFS [A, B, C, D, E, F, G].
      visit(neighbors[i]);
    }
  }

  visit(start);
  return result;
}

module.exports = { depthFirstSearch };

Three shifts separate this from the naive stack version. First, visited turns infinite cycles into finite traversals — every node is recorded exactly once, no matter how many edges point at it. Second, recursing in for-loop order (instead of pop()-ing off a stack) preserves the adjacency order the spec asks for. Third, the guard for "node missing from the map" and the || [] fallback for "dangling neighbor reference" handle the two shapes of "this node has no outgoing edges" — one where the node isn't keyed at all, one where it's keyed but the array is undefined.

Walking through one call

Trace depthFirstSearch(graph, 'A') on the seven-node tree from the diagram above (A: ['B', 'C'], B: ['D', 'E'], C: ['F', 'G'], leaves empty).

1. visit('A'). Not visited — add to set, push to result. result = ['A']. Loop over ['B', 'C'], recurse into 'B' first.
2. visit('B'). Not visited — add, push. result = ['A', 'B']. Loop over ['D', 'E'], recurse into 'D'.
3. visit('D'). Not visited — add, push. result = ['A', 'B', 'D']. Loop over [] — empty, so the function returns immediately. We're back in visit('B').
4. Still inside visit('B'), next iteration: recurse into 'E'. result = ['A', 'B', 'D', 'E']. E's neighbors are empty, return. visit('B')'s loop is done, return.
5. Back in visit('A'), next iteration: recurse into 'C'. result = ['A', 'B', 'D', 'E', 'C']. Loop over ['F', 'G'].
6. visit('F') then visit('G') — both leaves. result = ['A', 'B', 'D', 'E', 'C', 'F', 'G']. Each returns immediately.
7. visit('A')'s loop ends, return. Top-level call returns result.

Final output: ['A', 'B', 'D', 'E', 'C', 'F', 'G']. Notice D and E (B's whole subtree) finish before C is even touched — that's the depth-first signature.

Complexity. Time is O(V + E) — each node is visited once (the visited guard ensures it) and each edge is followed once. Space is O(V) for the visited set and result, plus O(d) on the call stack where d is the depth of the deepest path. On a pathological linear graph nested 50,000 deep, that call stack will blow — see Going further for the iterative version.

Gotchas

• Forgetting the visited set. Run the naive recursive version on A: ['B'], B: ['A'] and JavaScript throws RangeError: Maximum call stack size exceeded — visit('A') calls visit('B') calls visit('A') and so on until the engine gives up. The fix is the two-line guard at the top of visit: bail if visited.has(node), otherwise add it before recursing.
• Recording on the wrong side (pre-order vs post-order). This solution does result.push(node) before recursing — pre-order, which matches "visit order" as most people use the phrase. If you accidentally push after the loop, you get post-order ([D, E, B, F, G, C, A]), which is a legitimate traversal but not what the tests check. Push at entry, not exit.
• Iterating in pop() order with a stack. If you do build an iterative version with an explicit stack, you must push neighbors in reverse order so they pop in adjacency order. for (let i = neighbors.length - 1; i >= 0; i--) stack.push(neighbors[i]). Easy to forget; produces a working-but-wrong answer that flips child order on every level.
• Assuming every neighbor is a key. A graph like { A: ['B'] } (no key for B) is a real shape — B is a sink with no outgoing edges, encoded by absence. Reading graph['B'] returns undefined, and for (const n of undefined) throws. The || [] fallback or an explicit hasOwnProperty check stops the crash.
• Mutating the input. The natural temptation is to remove an edge from graph[node] after you visit it. Don't — the caller's data structure must survive the call intact. Track visited externally with the Set; leave graph alone.

Going further

• Iterative version with an explicit stack. Recursion blows up around 10–50k frames depending on the engine. For deep graphs, switch to a while (stack.length) loop pushing neighbors in reverse order so pop() preserves adjacency order. Same complexity, no call-stack ceiling.
• Return paths instead of just nodes. A small variation: pass an accumulator path down each branch and push [...currentPath, node] into the result. Useful for "find all paths from A to Z" or for printing the route to each leaf.
• Detect cycles while traversing. Track nodes that are currently on the recursion path in a second set (often called "gray" vs "black" in textbooks). If you ever hit a node that's still gray, you've closed a cycle — the basis for cycle detection and topological-sort algorithms like Kahn's and Tarjan's.