Trees and graphs

What it is and why it exists

A tree is a collection of nodes joined by parent-child edges. In a rooted tree, one node is the root, every other node has exactly one parent, and no edge sequence returns to a node already on that sequence. Those constraints create a hierarchy with one path from the root to every node.

A graph is the more general model: a set of vertices and a set of edges connecting them. An edge may be directed or undirected, and it may carry a label or weight. Graphs can contain cycles, several paths to one vertex, disconnected components, and vertices with no edges.

The names “node” and “vertex” are often interchangeable. Tree APIs usually say node because parent, child, ancestor, and descendant are central. Graph algorithms usually say vertex because an edge need not express ownership or hierarchy.

These models exist because many relationships cannot be represented honestly as one flat sequence. File systems, syntax trees, menus, and organizational units are naturally hierarchical. Package dependencies, road routes, social links, build steps, and web pages form general networks instead.

A tree is also a graph with additional invariants. This is useful because a tree algorithm can omit machinery that the invariants make unnecessary. Once a “tree” allows shared children, back-links, or several parents, however, it must be treated as a graph even if its records still have a field named children.

Traversal turns the model into an operation. It chooses a start vertex, visits reachable vertices in a defined strategy, and performs work such as collecting names, finding a target, validating dependencies, or reconstructing a route. The order is part of the algorithm’s contract, not a cosmetic detail.

Depth-first search and breadth-first search answer different questions. DFS follows one branch before returning, which matches recursive structure and backtracking. BFS visits by distance in edges from the start, which makes it the right baseline for shortest paths in an unweighted graph.

Before choosing either one, define what an edge means. A dependency edge may point from a service to what it needs or in the reverse direction. A road may be one-way. Reversing that convention changes reachability and can make correct traversal code answer the wrong business question.

How it works

Roots, vertices, and edges

A rooted tree gives traversal a natural starting point. A node with no children is a leaf; a node’s depth is the number of edges from the root. The tree’s height is the greatest node depth, although some APIs count levels instead and therefore differ by one.

A graph has no required root. The application supplies a start vertex, or it starts a traversal from every unvisited vertex when it must cover disconnected components. Reachability is always relative to edge direction and the chosen start.

The same five records can have different meanings under different edges:

The hierarchy has one incoming parent edge for each non-root node. The service network has two outgoing dependencies from Checkout and a cycle through Pricing and Tax. A visited set is optional for a proven tree but essential for a general graph traversal.

Representations are contracts

An object with nested children fields stores a tree directly. It makes downward traversal simple, but a child normally needs an explicit parent reference if code must move upward. Adding parent references creates a cycle in the in-memory object graph even though the logical data is still a tree.

An adjacency list maps each vertex to its outgoing neighbors. In JavaScript, a Map from stable identifiers to arrays is a direct representation. It stores only edges that exist and makes neighbor iteration explicit.

An adjacency matrix gives every ordered pair of vertices a cell. It makes an edge existence check direct but allocates space for all pairs, including missing edges. This can be appropriate for a small dense graph, whereas an adjacency list usually fits sparse dependency and route data better.

Vertex identity deserves an explicit rule. Two object instances may describe the same database entity, while two records with the same display name may be distinct. A traversal’s visited set should use the stable identity that the domain treats as one vertex, such as a service ID or station code.

Neighbor order also affects observable traversal order. DFS and BFS specify which frontier to process next, not how unordered neighbors should be arranged. If output order matters, store an order, sort with a documented key, or state that any valid order is acceptable.

Depth-first search uses a stack

Depth-first search takes one unvisited neighbor and continues from it before returning to alternatives. Recursive DFS uses the language’s call stack. Iterative DFS stores the same pending work in an explicit stack and avoids tying graph depth to the runtime recursion limit.

A basic iterative DFS follows this state transition:

1. Put the start vertex on a stack.
2. Pop one vertex; skip it if it has already been visited.
3. Mark it visited and perform the visit action.
4. Push its neighbors in the reverse of the desired visitation order.
5. Continue until the stack is empty.

Pushing in reverse matters because a stack is last-in, first-out. If neighbors are [pricing, inventory] and pricing should be visited first, push inventory and then pricing. A recursive loop visits the array from left to right without this reversal because each call completes before the loop advances.

DFS is a natural fit for evaluating recursive structure, finding connected components, detecting cycles, and exploring a search space with backtracking. Plain DFS visitation order is not automatically a dependency installation order. Topological sorting needs a directed acyclic graph and records completion order, not merely discovery order.

Breadth-first search uses a queue

Breadth-first search visits the start, then vertices one edge away, then vertices two edges away, and so on. A queue preserves this layer order. Enqueueing an unvisited neighbor records work for a later layer while older queued vertices remain first.

A basic BFS follows a slightly different transition:

1. Mark the start seen and enqueue it.
2. Dequeue one vertex and perform the visit action.
3. For each unseen neighbor, mark it seen, record its parent if needed, and enqueue it.
4. Continue until the queue is empty or the requested goal is reached.

Marking on enqueue prevents two vertices in the same layer from adding the same neighbor twice. It also makes the first recorded parent the one that discovered the vertex at minimum edge distance. Marking only after dequeue can duplicate frontier entries and complicate parent reconstruction.

In an unweighted graph, BFS discovers every reachable vertex using the fewest edges from the start. A parent map stores the edge by which each vertex was first discovered. Following parents backward from a goal and reversing the collected sequence reconstructs one shortest path.

This guarantee counts edges, not time, price, or risk. If edges have unequal costs, a two-edge route can be worse than a three-edge route. Nonnegative weighted shortest paths require an algorithm such as Dijkstra’s, together with a priority queue and a precise weight contract.

Visited state makes traversal finite

A visited set records semantic vertex identity, not how many paths lead there. On a cycle A -> B -> C -> A, the second encounter with A stops that branch. On a diamond, it prevents a shared destination from being fully processed once through each parent.

Sometimes one Boolean state is insufficient. Directed cycle detection distinguishes unseen vertices, vertices active on the current DFS path, and fully completed vertices. Encountering an active vertex is a back edge and proves a directed cycle; encountering a completed vertex does not.

Traversal state should belong to one traversal unless the API deliberately maintains an index across calls. Reusing a visited set accidentally can make a second search skip valid vertices. Hiding the set in module state also makes concurrent or interleaved traversals interfere with each other.

Examples

These examples use only built-in JavaScript collections. Each file was executed with local Node 24, and each text block is the resulting standard output.

Rendering a category tree in preorder

The catalog is a rooted tree represented by nested children. Preorder visits a node before its descendants, so the parent label is available before indented child lines are emitted.

Every recursive call receives a depth owned by its path, so sibling nodes use the same indentation and children add one level. The code relies on the tree contract: each record has a children array and no child points back to an ancestor.

If data comes from an API, validate those assumptions before recursion. A missing children field is a schema error; a cycle means the logical input is a graph and requires visited tracking or rejection.

Walking cyclic service dependencies with DFS

This adjacency list contains pricing -> tax -> catalog -> pricing. The visited set makes the walk terminate, while the explicit stack removes dependence on the call stack.

const dependencies = new Map([
  ["checkout", ["pricing", "inventory"]],
  ["pricing", ["tax"]],
  ["tax", ["catalog"]],
  ["catalog", ["pricing"]],
  ["inventory", ["catalog"]],
]);

function depthFirst(graph, start) {
  const visited = new Set();
  const order = [];
  const stack = [start];

  while (stack.length > 0) {
    const service = stack.pop();
    if (visited.has(service)) continue;

    visited.add(service);
    order.push(service);

    const next = graph.get(service) ?? [];
    for (let index = next.length - 1; index >= 0; index -= 1) {
      stack.push(next[index]);
    }
  }

  return order;
}

console.log(depthFirst(dependencies, "checkout").join(" -> "));

checkout -> pricing -> tax -> catalog -> inventory

Reversing neighbor pushes preserves the adjacency arrays’ left-to-right order in this DFS result. The result is a reachability order only. The cycle means no valid topological order exists, and this function does not attempt to produce one.

The ?? [] policy treats a missing map entry as a vertex with no outgoing edges. That may be convenient for partial data, but a dependency validator might instead report every referenced service that lacks its own entry.

Reconstructing an unweighted route with BFS

The route map uses directed connections. BFS records a parent when a place is first enqueued, then follows those parents backward only if the goal was discovered.

const routes = new Map([
  ["Depot", ["Museum", "Station"]],
  ["Museum", ["Park"]],
  ["Station", ["Harbor"]],
  ["Park", ["Harbor"]],
  ["Harbor", []],
]);

function shortestPath(graph, start, goal) {
  const queue = [start];
  const seen = new Set([start]);
  const parent = new Map([[start, null]]);
  let head = 0;

  while (head < queue.length) {
    const place = queue[head];
    head += 1;
    if (place === goal) break;

    for (const neighbor of graph.get(place) ?? []) {
      if (seen.has(neighbor)) continue;
      seen.add(neighbor);
      parent.set(neighbor, place);
      queue.push(neighbor);
    }
  }

  if (!parent.has(goal)) return null;

  const path = [];
  for (let place = goal; place !== null; place = parent.get(place)) {
    path.push(place);
  }
  return path.reverse();
}

const harborRoute = shortestPath(routes, "Depot", "Harbor");
const airportRoute = shortestPath(routes, "Depot", "Airport");
console.log(harborRoute.join(" -> "));
console.log(airportRoute ?? "No route");

Depot -> Station -> Harbor
No route

Harbor is first discovered from Station, at distance two. The alternative through Museum and Park uses three edges and cannot replace that parent. An absent target returns null rather than a partial route.

The head index avoids removing the first array element on every dequeue. The consumed prefix remains allocated until the function returns, which is appropriate for this bounded traversal. A long-lived streaming queue should use a queue abstraction that can reclaim storage.

Pitfalls

Treating graph data as a tree

Fix: validate a promised tree at its boundary, or traverse it as a graph with stable vertex identities. Test a self-loop, a two-vertex cycle, and a diamond in which two parents share one destination.

Marking BFS vertices after dequeue

Fix: mark a neighbor seen in the same step that enqueues it, and set its parent once. Test a diamond graph and assert both the path and the number of queued vertices.

Using an array front as an unbounded queue

Fix: keep a head index for a traversal-scoped array, as in the route example, or use a tested deque for a long-lived queue. Put an explicit bound on externally supplied graph size.

Calling BFS a weighted shortest-path algorithm

Fix: state whether every edge has equal cost. Use a suitable weighted algorithm for nonnegative weights, reject invalid weights, and test a case where the cheapest route has more edges.

Mistaking DFS discovery order for dependency order

Fix: request topological sorting explicitly, use three-state cycle detection, and fail with a useful cycle path. Test independent components as well as a dependency cycle.

Recursing over unbounded depth

Fix: use an explicit stack when depth is not tightly bounded, and enforce input limits appropriate to the service. Test a long chain rather than only balanced sample trees.

Further reading

• MDN: Map
• MDN: Set
• NIST Dictionary: breadth-first search
• NIST Dictionary: depth-first search
• Princeton Algorithms: graphs