BFS and DFS on trees and graphs

Tree code on a graph repeats or loops; a visited set makes each node one visit, and a path set finds the cycles.

Before you read: predict

ExamHall's admin app lists every section a candidate must pass before the final. Two mid-terms share their quizzes, and the quizzes share their readings:

How many entries does list hold?

const prereqs = {  final: ['midA', 'midB'],  midA: ['quizA', 'quizB'],  midB: ['quizA', 'quizB'],  quizA: ['readA', 'readB'],  quizB: ['readA', 'readB'],  readA: ['intro'],  readB: ['intro'],  intro: [],};function collect(id, out) {  for (const p of prereqs[id]) {    out.push(p);    collect(p, out);  }  return out;}export const list = collect('final', []);

The 30-second version

DFS goes deep, by recursion or a stack. BFS goes level by level with a queue and reaches each node first by the fewest edges. On a graph keep a visited set, or a shared node repeats once per path and a cycle never ends. A build order lists a node after its prerequisites.

Tree code on a graph repeats or loops; a visited set makes each node one visit, and a path set finds the cycles.

How it works

Step 1 of 10

A tree has one path to each node; a graph may have many, and may loop. Code written for trees assumes the first.

Analogy: A village's rice-terrace channels at flooding time (water engineering)

On the terraces	In the code
a farmer walks one channel down to its last paddy, then back up to the last fork to try the next	DFS (step 2)
water let in at the top reaches the paddies one channel further each hour; the hour it arrives counts the fewest channels	BFS and fewest edges (steps 3, 4)
a paddy fed by two channels gets a flag in its bank the first time it is reached, so it is counted once	a visited set (step 5)
the flag goes in when the sluice to that paddy is opened, not when the water arrives, so no second sluice is opened into it	marking on enqueue (step 6)
a paddy is flooded only after every paddy above that feeds it is full	topological order (step 8)

In real terms: a walk is a rule for which node to take next; a visited set and a path set say which nodes are already done and which are still open.

Breaks down when: water fills every channel at once, while code takes one node at a time; and water cannot run uphill, while a graph's edges can loop back.

Contrasting case: a single row of paddies, one below the next. There is one path, so deep and wide walks meet the same paddies in the same order, and a flag is never needed.

Examples, run for real

4.1 ExamHall EXH-4260: a cyclic configuration crashes the unlock check

ExamHall's admin app checked "unlock C after A and B" by collecting each section's prerequisites recursively, with no state. An admin edit made essay need review while review already needed essay (EXH-4260):

4.1 EXH-4260 the old check on the saved configuration (essay needs review, review needs essay): RangeError: Maximum call stack size exceeded
4.1 MR !4560 buildOrder on the same configuration: Error: cycle at essay (refused before saving)
4.1 MR !4560 buildOrder once review needs nothing: review essay intro quiz final (each section after its prerequisites)

The old walk remembered nothing, so the loop ran until the call stack ran out (step 5). MR !4560 replaces it with a depth-first buildOrder (step 9): the cyclic edit is refused with a message naming the section, and a valid configuration comes back as an order in which every section follows its prerequisites (step 8).

4.2 Payments: fewest transfers between two accounts

A treasury desk wants the fewest transfers from ops to vendor. BFS walks the accounts level by level from ops:

4.2 BFS from ops: level 1 payroll treasury · level 2 bankB vendor audit · vendor at 2 transfers
4.2 BFS queue entries: 6 for 6 accounts (each marked when enqueued)

BFS reaches vendor first at level 2, by a shortest route (step 4). Marked on enqueue, each account enters BFS's queue once (step 6).

Try it

Answer first, then check. Nothing is saved.

Question 1 of 8

A chat app shows how many hops a contact is from you: 1 for a contact, 2 for a contact's contact, and so on. Its hopsTo function is complete apart from the neighbour loop:

In what order does the loop body run them, top first?

export function hopsTo(graph, start, target) {  if (start === target) return 0;  const dist = new Map([[start, 0]]);  const queue = [start];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    /* the five lines, in order */  }  return -1;}

Your order

1empty
2empty
3empty
4empty
5empty

Tap the lines in the order you expect.

Question 2 of 8

A ledger stores which accounts can pay which. A recursive search looks for a route of transfers from acmeOps to vendorX:

What is result?

const links = {  acmeOps: ['payroll', 'bankA', 'escrow'],  payroll: ['staff'],  staff: ['bankB'],  bankB: ['vendorX'],  bankA: ['vendorX'],  escrow: ['trust'],  trust: ['clearing'],  clearing: ['vendorX'],  vendorX: [],};function route(from, to, seen = new Set()) {  if (from === to) return [to];  seen.add(from);  for (const next of links[from]) {    if (seen.has(next)) continue;    const rest = route(next, to, seen);    if (rest) return [from, ...rest];  }  return null;}export const result = route('acmeOps', 'vendorX').join(' ');

Question 3 of 8

A video app walks its "related videos" links breadth-first from the video being watched. It marks a video when it takes it out of the queue:

How many entries has queue held by the end?

const related = {  v0: ['v1', 'v2', 'v3'],  v1: ['v2', 'v4'],  v2: ['v3', 'v4'],  v3: ['v1', 'v4', 'v0'],  v4: ['v0'],};const seen = new Set();const queue = ['v0'];for (let head = 0; head < queue.length; head++) {  const video = queue[head];  if (seen.has(video)) continue;  seen.add(video);  for (const next of related[video]) if (!seen.has(next)) queue.push(next);}export { queue };

Question 4 of 8

ExamHall's unlock check (MR !4560) is complete apart from its first line:

The team's list has 10 tests: valid orders for chains, shared and unlinked sections, and a cycle error for a section needing itself, two needing each other, and longer loops.

Which check passes all 10?

export function buildOrder(prereqs) {  const done = new Set();  const onPath = new Set();  const order = [];  function visit(id) {    /* the check */    if (done.has(id)) return;    onPath.add(id);    for (const p of prereqs[id] ?? []) visit(p);    onPath.delete(id);    done.add(id);    order.push(id);  }  for (const id of Object.keys(prereqs)) visit(id);  return order;}

Question 5 of 8

the interviewer says: "ExamHall admins set prerequisites per section, like { final: ['mid'], mid: ['quiz'] }. Write buildLevels(prereqs): return the sections in rounds, an array of arrays. The first round holds every section with no prerequisites; each later round holds every section whose prerequisites all sit in earlier rounds, as early as it can go. Throw an error starting with cycle if the configuration loops." You have 15 minutes and a plain editor.

Before you type: say your test list out loud.

Name at least six tests, each with its input and what it expects.

Your answer (optional, stays on this page)

Question 6 of 8

Now write it, in 15 minutes, from a blank file that exports buildLevels.

Your answer (optional, stays on this page)

Question 7 of 8

A venue's set-up app orders the jobs before doors open with this kata answer:

What is plan?

export function buildOrder(prereqs) {  const done = new Set();  const onPath = new Set();  const order = [];  function visit(id) {    if (onPath.has(id)) throw new Error('cycle at ' + id);    if (done.has(id)) return;    onPath.add(id);    for (const p of prereqs[id] ?? []) visit(p);    onPath.delete(id);    done.add(id);    order.push(id);  }  for (const id of Object.keys(prereqs)) visit(id);  return order;}const jobs = {  doors: ['stage', 'security'],  stage: ['rigging'],  security: ['rigging', 'barriers'],  rigging: [],  barriers: [],};export const plan = buildOrder(jobs).join(' ');

Question 8 of 8

A chat workspace updates its unread counts; each group's count needs its sub-channels' counts first, and two groups share two channels:

How many times is update called?

const feeds = {  workspace: ['eng', 'sales'],  eng: ['general', 'alerts'],  sales: ['general', 'alerts'],  general: ['announce'],  alerts: ['announce'],  announce: [],};let calls = 0;const done = new Set();function update(id) {  calls++;  if (done.has(id)) return;  for (const f of feeds[id]) update(f);  done.add(id);}for (const id of Object.keys(feeds)) update(id);export { calls };

Go deeper

Pro tips

Ask "tree or graph?" before you write the walk. When: the input is a list of links, not a nested object (step 1). Can two parents share a child, or a link point back? If so, add the visited set before anything else. Verify (RAN, tips.mjs):
```
tip 1 a two-link loop: tree walk RangeError · with a visited set 2 visits, then it ends
```
Say the corner cases out loud: an empty graph, one node, two unlinked parts, a cycle. When: before running your walk in an interview. Verify (RAN, tips.mjs):
```
tip 2 buildOrder on the corner cases: empty [] · one node [a] · two unlinked [a, b] · a cycle cycle at a
```

Source

Vendor pages change, so their claims are labelled as of 2026-10-15; every count this lesson grades is executed on Node 24. The curriculum row's first source, Cormen et al., is a book and keys nothing.

Tech Interview Handbook, Graph cheatsheet (the curriculum row's second source), https://www.techinterviewhandbook.org/algorithms/graph/ (tih-graph.txt). As of 2026-10-15.
- "Depth-first search is a graph traversal algorithm which explores as far as possible along each branch before backtracking." (step 2)
- "This can be done either by an implicit recursion stack, or an actual stack data structure." (step 2)
- "A queue is usually used to keep track of the nodes that were encountered but not yet explored." (step 3)
- "A tree-like diagram could very well be a graph that allows for cycles and a naive recursive solution would not work." (steps 1, 5)
- "Ensure you are correctly keeping track of visited nodes and not visiting each node more than once. Otherwise your code could end up in an infinite loop." (step 5)
- "Depth-first searchO(|V| + |E|)" (step 7; the page's table, cells run together in the saved text)
- "Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited." (step 8)
- "When traversing the matrix, always ensure that your current position is within the boundary of the matrix and has not been visited before." (step 10)
- Its corner cases (tip 2): "Empty graph", "Graph with one or two nodes", "Disconnected graphs", "Graph with cycles".
The page's own BFS template marks a cell visited when it is taken out of the queue (if (curr_i, curr_j) not in visited: visited.add(...)), the form P3 serves; step 6 and the curriculum row's pro tip mark on enqueue instead. Both give the same levels; they differ in queue entries, which P3 counts.

Checked against the tools and docs as of 2026-10-15.

Predict first