intermediate

Review: the traversal that never comes back

This is recall. The code looks finished and is wrong. Find the defect and fix it. You are graded on tests you cannot see.

The build tool walks a dependency graph to compute everything a package transitively needs. The walker below is a clean recursive depth-first traversal, and it passed every test — because every test graph was acyclic.

/**
 * Returns every node reachable from `from` through the directed edges,
 * including `from` itself, in traversal order.
 */
export function reachable(edges: Array<[string, string]>, from: string): string[] {
  const adjacency = new Map<string, string[]>()
  for (const [a, b] of edges) {
    const links = adjacency.get(a) ?? []
    links.push(b)
    adjacency.set(a, links)
  }

  const out: string[] = []

  function walk(node: string): void {
    out.push(node)
    for (const next of adjacency.get(node) ?? []) {
      walk(next)
    }
  }

  walk(from)
  return out
}

review — find the defectCtrl+↵ submits · Ctrl+Shift+↵ runsstarter code