
A tree is a hierarchy: each node has a value and zero or more children, and there is exactly one root. There are no cycles and no second path to the same node. The DOM, a file system, and a JSON document are all trees.

<ExamplePair>
<ExampleProse>

The simplest representation is a plain object with a `value` field and a `children` array. A recursive `walk` function visits the root, then calls itself on each child. Tracking `depth` lets you add indentation so the printed output mirrors the hierarchy visually.

</ExampleProse>
<ExampleCode>

```js
const fileSystem = {
  value: "root",
  children: [
    {
      value: "src",
      children: [
        { value: "index.js", children: [] },
        { value: "utils.js", children: [] },
      ],
    },
    {
      value: "public",
      children: [
        { value: "index.html", children: [] },
        { value: "logo.svg",   children: [] },
      ],
    },
    { value: "package.json", children: [] },
  ],
};

function walk(node, depth = 0) {
  console.log(" ".repeat(depth * 2) + node.value);
  for (const child of node.children) {
    walk(child, depth + 1); // recurse into each child
  }
}

walk(fileSystem);
// root
//   src
//     index.js
//     utils.js
//   public
//     index.html
//     logo.svg
//   package.json
```

</ExampleCode>
</ExamplePair>

<ExamplePair>
<ExampleProse>

Recursive traversal has an implicit stack living in the call stack. When the tree comes from user input it can be arbitrarily deep, and deep recursion throws a `RangeError: Maximum call stack size exceeded`. An iterative DFS replaces the call stack with an explicit array used as a stack: push the root, then loop - pop a node, process it, push its children.

</ExampleProse>
<ExampleCode>

```js
function walkIterative(root) {
  const stack = [{ node: root, depth: 0 }];

  while (stack.length > 0) {
    const { node, depth } = stack.pop(); // take from the top
    console.log(" ".repeat(depth * 2) + node.value);

    // push children in reverse order so the first child is processed first
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push({ node: node.children[i], depth: depth + 1 });
    }
  }
}

// same output as the recursive version, but safe on deep trees
walkIterative(fileSystem);
// root
//   src
//     index.js
//     utils.js
//   public
//     index.html
//     logo.svg
//   package.json

// the recursive version would throw on deeply nested user data:
// RangeError: Maximum call stack size exceeded
```

</ExampleCode>
</ExamplePair>

<InProduction>
Recursive traversal blows the call stack on deep user-supplied trees - HTML pasted from a document editor or badly nested JSON can easily exceed the default stack depth in V8 (~10,000 frames). Iterative DFS with an explicit stack is the safe default whenever depth is unbounded. For the DOM specifically, `TreeWalker` (`document.createTreeWalker`) is purpose-built, iterative, and faster than any hand-rolled traversal.
</InProduction>


Tree: a hierarchy with one root where each node has a value and children. Recursive traversal is elegant but unsafe on deep user data; use iterative DFS with an explicit stack.

Trees


A graph is a set of nodes connected by edges. Unlike a tree, a graph can have cycles (a chain of edges that loops back to a node you already visited) and more than one path between any two nodes. Social networks, package dependency graphs, and route maps are all graphs.

<ExamplePair>
<ExampleProse>

An adjacency list represents a graph as a `Map` where each key is a node and its value is the array of nodes it connects to. For an undirected graph you add an entry in both directions. This representation uses space proportional to the number of edges, which makes it efficient for sparse graphs where most nodes are not directly connected to each other.

</ExampleProse>
<ExampleCode>

```js
const graph = new Map();

function addEdge(a, b) {
  if (!graph.has(a)) graph.set(a, []);
  if (!graph.has(b)) graph.set(b, []);
  graph.get(a).push(b); // undirected: add both directions
  graph.get(b).push(a);
}

addEdge("alice",   "bob");
addEdge("alice",   "carol");
addEdge("bob",     "dave");
addEdge("carol",   "dave");

// graph:
//  alice  ->  bob, carol
//  bob    ->  alice, dave
//  carol  ->  alice, dave
//  dave   ->  bob, carol

for (const [node, neighbors] of graph) {
  console.log(`${node}: ${neighbors.join(", ")}`);
}
// alice: bob, carol
// bob: alice, dave
// carol: alice, dave
// dave: bob, carol
```

</ExampleCode>
</ExamplePair>

<ExamplePair>
<ExampleProse>

Breadth-first search (BFS) explores nodes level by level using a queue. A `visited` Set prevents revisiting nodes; without it, any cycle in the graph turns the traversal into an infinite loop. Removing the Set from this example and adding an edge that creates a cycle shows the problem immediately.

</ExampleProse>
<ExampleCode>

```js
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // take from the front (FIFO)
    console.log("visited:", node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);   // mark before enqueue to avoid duplicates
        queue.push(neighbor);
      }
    }
  }
}

bfs(graph, "alice");
// visited: alice
// visited: bob
// visited: carol
// visited: dave

// WITHOUT the visited Set, alice -> bob -> alice -> bob -> ...
// => infinite loop because the graph has a cycle (alice <-> bob)
```

</ExampleCode>
</ExamplePair>

<InProduction>
Any graph traversal needs cycle detection via a `visited` Set or it will infinite-loop on real data - production graphs (dependency trees, social graphs, route networks) nearly always contain cycles. Adjacency lists are the right default: they use O(nodes + edges) space, which is efficient for sparse graphs where most pairs of nodes are not directly connected. Adjacency matrices use O(nodes²) space and only beat adjacency lists when the graph is dense and you need constant-time edge lookup between arbitrary node pairs.
</InProduction>


Graph: nodes connected by edges, with cycles and multiple paths. Always carry a visited Set or a cycle will infinite-loop your traversal. Adjacency lists are the right default.

Graphs


A linked list is a chain of nodes; each node holds a value and a reference (pointer) to the next node. There is no underlying contiguous block of memory, which means inserting or removing a node at a known position is O(1) - you just rewire two pointers. The trade-off is that there is no index: to get item number 50 you have to follow the chain 50 times.

<ExamplePair>
<ExampleProse>

A minimal singly-linked list needs a `Node` class and a `LinkedList` class. `prepend` adds to the front in O(1). `append` walks to the last node and attaches there - O(n). An iteration helper (or a standard `[Symbol.iterator]`) lets you loop over the values with a `for...of` loop.

</ExampleProse>
<ExampleCode>

```js
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next; // walk to the last node
      }
      current.next = node;
    }
    this.size++;
  }

  [Symbol.iterator]() {
    let current = this.head;
    return {
      next() {
        if (!current) return { done: true, value: undefined };
        const value = current.value;
        current = current.next;
        return { done: false, value };
      },
    };
  }
}

const list = new LinkedList();
list.append("a");
list.append("b");
list.append("c");

for (const val of list) {
  console.log(val); // "a", "b", "c"
}

console.log(list.size); // 3
```

</ExampleCode>
</ExamplePair>

<ExamplePair>
<ExampleProse>

The key limitation of a linked list is the absence of random access. Getting the item at index `i` requires starting at the head and following `i` pointers. With an array the same operation returns instantly because the runtime can compute the memory address directly from the index.

</ExampleProse>
<ExampleCode>

```js
class LinkedList {
  // ... (same as above)
  get(index) {
    let current = this.head;
    let i = 0;
    while (current) {
      if (i === index) return current.value;
      current = current.next;
      i++;
    }
    return undefined; // index out of bounds
  }
}

// Linked list: O(n) - must walk from the head
const list = new LinkedList();
for (let i = 0; i < 1000; i++) list.append(i);
console.log(list.get(999)); // 999 - walked 1000 nodes

// Array: O(1) - computed from base address + offset
const arr = Array.from({ length: 1000 }, (_, i) => i);
console.log(arr[999]); // 999 - instant lookup
```

</ExampleCode>
</ExamplePair>

<InProduction>
Pointer chasing (following a chain of references scattered across the heap) destroys CPU cache locality: each node read is likely a cache miss, which is far slower than reading a contiguous array. In V8, arrays win for almost every application-code use case. The real production scenario where a linked list earns its keep is a doubly-linked list inside an LRU cache: you need O(1) insertion and O(1) removal at arbitrary positions, and you always have a direct reference to the node you want to move, so you never have to scan.
</InProduction>


Linked list: nodes chained via pointers. O(1) insert/remove at known positions, but no random access - walking n nodes to reach index i means arrays win for most application code.