DFS Graph Traversal

The problem

Implement `dfs(graph, source)` — same adjacency-list shape as BFS — returning every reachable node in depth-first order.

For `{ a: ['c', 'b'], b: ['d'], c: ['e'], d: [], e: [] }` starting at `a`, the expected order is `['a', 'b', 'd', 'c', 'e']`. Note `a`'s neighbour list is `['c', 'b']` but `b` comes out before `c` — that's the LIFO ordering, not a typo.

The approach

Same shape as the BFS solution, but `stack.pop()` instead of `q.shift()`. Popping takes the *most recently pushed* node, so the traversal dives down one branch fully before backing up to try the next.

The reversal is the subtle part: `a`'s neighbours are pushed in listed order (`c`, then `b`), so the stack is `[c, b]` with `b` on top — `b` gets popped and explored first, even though `c` was listed first. A recursive DFS visiting neighbours in listed order would hit `c` before `b`; this iterative version, because it stacks all of `source`'s neighbours before descending, effectively visits them right-to-left.

As with the BFS version, there's no `visited` set — safe only because the test graphs are trees with no shared or cyclic edges.

The solution

export function dfs(graph, source) {
    const stack = [source]
    const result = []
    while (stack.length) {
        const node = stack.pop()
        result.push(node)
        for (let neighbour of graph[node]) {
            stack.push(neighbour)
        }
    }
    return result
}

Time O(V + E)Space O(V)