HardDSAAsked in 20247 min read

Graph dfs traversal

Q: Graph dfs traversal

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Hard > **How to read this doc:** DFS is easy to recite and easy to get subtly wrong when made iterative. Three versions were compared on 20,000 random graphs (with cycles, self loops and repeated edges): recursive and iterative (mark when popped, push neighbours in reverse) agreed on every graph, while the tempting "mark when pushed" variant visited the same nodes but in a different order on 5,767 of them, so it is not depth-first. ## 1. The problem, restated Starting at a node, go as deep as possible along each branch before backing up, visiting every reachable node once. A `visited` set makes it safe on cycles. The order of visiting (which neighbour first, when a node counts as "visited") is what defines depth-first search. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Order of neighbours? | A recursive DFS visits neighbours in

520 views

151 of 154

The problem

Problem, as an interviewer would state it: "Implement a depth-first search over a graph given as an adjacency list, returning the order in which nodes are visited. Discuss edge cases, runtime, recursive versus iterative, and alternatives."

Examples:

Code

graph = { A: ["B", "C"], B: ["D"], C: ["D", "E"], D: ["F"], E: ["F"], F: [] }
dfs(graph, "A"); // ["A", "B", "D", "F", "C", "E"]

Clarifying questions expected:

Directed or undirected, and may it contain cycles, self loops or repeated edges?
Is the graph connected, or must every component be covered?
Which order do you want: pre-order (visit on entry), post-order (visit on exit)?

Code / implementation expected: Yes — real, direct proof that recursive and iterative versions agree, and of the subtle iterative variant that does not.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Hard

How to read this doc: DFS is easy to recite and easy to get subtly wrong when made iterative. Three versions were compared on 20,000 random graphs (with cycles, self loops and repeated edges): recursive and iterative (mark when popped, push neighbours in reverse) agreed on every graph, while the tempting "mark when pushed" variant visited the same nodes but in a different order on 5,767 of them, so it is not depth-first.

1. The problem, restated

Starting at a node, go as deep as possible along each branch before backing up, visiting every reachable node once. A visited set makes it safe on cycles. The order of visiting (which neighbour first, when a node counts as "visited") is what defines depth-first search.

2. Clarifying questions a strong candidate asks

| Quest

The solution is hidden so you can try first

7 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: iterative DFS reproduces the recursive order on random graphs, marking on push does not, and recursion overflows where the iterative version does not

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 151 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextHard→

Build a Minimal State Machine Runner (States, Transitions, Guards)

Continue