Trees & graph traversal

Trees and graphs model relationships: a file system, a social network, a dependency graph, a maze. A tree is just a graph with no cycles and a single root. The most common representation is an adjacency list, a map from each node to the list of its neighbors. It uses space proportional to nodes plus edges, which is far leaner than an adjacency matrix for the sparse graphs you usually meet.

// adjacency list: node -> its neighbors
const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"],
};

Breadth-first versus depth-first

Breadth-first search explores level by level using a queue, visiting all nodes one hop away before any node two hops away. That ordering is exactly why it finds the shortest path in number of hops on an unweighted graph. Depth-first search follows one path as far as it goes using a stack or recursion, then backtracks. Use depth-first when you need to visit everything, detect cycles, or explore a full subtree; use breadth-first when you care about distance from a starting node.

Always track visited

The single most common graph bug is revisiting nodes and looping forever. Keep a Set of visited nodes and skip any node already in it. In breadth-first search you mark a node visited when you enqueue it, not when you dequeue it, so it is never added twice. With visited tracking, every node and edge is processed once, giving order nodes-plus-edges time.

The challenge runs breadth-first search over an adjacency list and returns the shortest number of hops between two nodes, tracking visited nodes and the distance to each.

You now have the core patterns: complexity, hash maps, two pointers and windows, stacks and queues, and graph traversal. These five cover the majority of interview problems and most everyday algorithmic judgment.