Building the graph, and DFS without recursion

Building the graph you traverse

Lessons 7-1 and 7-2 handed you a ready-made adjacency dictionary. Real problems almost never do. Interview inputs arrive as an edge list — pairs like ("A", "B") — or as a grid, and the first minute of your solution is building the adjacency list. Getting this step wrong (usually by forgetting one direction of an undirected edge) produces a traversal that silently misses half the graph, so the step deserves its own drill.

The recipe:

1. Start an empty defaultdict(list) — a dictionary that invents an empty list for any new key, saving an if-statement per node.
2. For each edge (u, v): append v to u's list. If the graph is undirected (friendships, roads), also append u to v's list — one edge, two entries.
3. Directed edges (follows, prerequisites) get only the one entry.

Cost: O(E) to build, and the result answers "who are my neighbors?" in O(1) — which is why BFS and DFS take adjacency lists, not raw edge lists, as input.

DFS without recursion

Recursive DFS borrows Python's call stack, and Python caps that stack at about 1,000 frames — beyond it you get a RecursionError (the cap exists to catch runaway recursion before it exhausts memory). A path-shaped graph with 10,000 nodes goes 10,000 calls deep and hits the cap. The fix: manage the stack yourself. Keep a plain list, push the start node, then loop — pop a node, push its unseen neighbors. list.append and list.pop ARE the push and pop from Data Structures, and a list on the heap can hold millions of entries where the call stack held a thousand.

Same visited-set rule, same O(V + E) cost, same depth-first behavior: the most recently discovered node is always explored next. This skeleton is also one swap away from BFS — replace the stack's pop-from-the-end with a queue's pop-from-the-front and the traversal order flips from deepest-first to nearest-first.