SyntaxPilot
Courses/JavaScript/Lesson 36
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript · Lesson 36 of 40

DSA in JS 3: trees and graphs

queued

These are the notes for JavaScript episode 36, part three of data structures. A linked list node had one next; today a node points to many others. Counting the files in Neha's nested folders with one loop gives 15 instead of 24, so we invent trees and recursion. A binary search tree finds a roll number in a few steps, until sorted input turns it into a line, so we build it from the middle. A metro map becomes a graph; walking it like a tree crashes with Maximum call stack size exceeded, a visited set fixes it (DFS), and a queue gives the route with the fewest stops (BFS). Every output below is real Node.js output (Node 24). Long stack traces are shortened with ....

Builds on: objects and arrays (episodes 7, 8), functions and default parameters (9), Map and Set (21), Big O, stacks and queues (34), linked lists (35). Leads to: DSA in JavaScript 4: sorting and searching (37).

Neha's laptop: nested folders

Folder Its own files Inside it
Documents 2 College, Photos
College 3 Sem1, Sem2
Sem1 5 nothing
Sem2 4 nothing
Photos 10 nothing

Neha needs the total before a backup: 2 + 3 + 5 + 4 + 10 = 24.

The obvious attempt: one loop

const laptop = {
  name: "Documents", files: 2, children: [
    { name: "College", files: 3, children: [
      { name: "Sem1", files: 5, children: [] },
      { name: "Sem2", files: 4, children: [] },
    ] },
    { name: "Photos", files: 10, children: [] },
  ],
};
let total = laptop.files;
for (const child of laptop.children) total += child.files;
console.log("Total files:", total);

Output:

Total files: 15

Why it's wrong: one loop sees one level. Sem1 and Sem2 are two levels down. Folders can nest to any depth, so no fixed number of nested loops is ever enough.

Trees

A tree is a set of nodes where each node has a list of children. Words you need:

Term Meaning In Neha's laptop
root the top node, with no parent Documents
child a node directly below another College is a child of Documents
parent the node directly above College is the parent of Sem1
leaf a node with no children Sem1, Sem2, Photos
subtree a node and everything below it College with Sem1 and Sem2
depth of a node how many levels below the root it is Sem1 is at depth 2
height of a tree the number of levels on the longest path 3 (Documents → College → Sem1)

Trees have no loops: following children always goes down and eventually stops at leaves. File systems, the HTML page structure (the DOM), company org charts and JSON objects are all trees.

Recursion

Say the answer in words: the files in a folder are its own files, plus the files in each child folder. And each child folder is a smaller tree: the same question again. A function that solves a problem by calling itself on smaller parts is recursive. Every recursive function needs:

  1. a base case, where it stops without calling itself (here: a leaf, whose loop has nothing to visit), and
  2. a recursive case that moves towards the base case (here: each call is on a smaller subtree).
function countFiles(folder) {
  let total = folder.files;
  for (const child of folder.children) total += countFiles(child);
  return total;
}
function show(folder, depth = 0) {
  console.log("  ".repeat(depth) + folder.name + " (" + folder.files + ")");
  for (const child of folder.children) show(child, depth + 1);
}
console.log("Total files:", countFiles(laptop));
show(laptop);

Output:

Total files: 24
Documents (2)
  College (3)
    Sem1 (5)
    Sem2 (4)
  Photos (10)

How countFiles(laptop) unfolds:

countFiles(Documents) = 2 + countFiles(College) + countFiles(Photos)
countFiles(College)   = 3 + countFiles(Sem1) + countFiles(Sem2) = 3 + 5 + 4 = 12
countFiles(Photos)    = 10
countFiles(Documents) = 2 + 12 + 10 = 24

show finishes all of College before it visits Photos: going as deep as possible first is called depth-first order. Each waiting call sits on the call stack (episode 34) until its children return. Visiting every node once makes both functions O(n).

Binary search trees

A teacher looking for roll 60 starts at the middle roll, 50. 60 is bigger, so she goes right. In a binary tree every node has at most two children, left and right. A binary search tree (BST) adds a rule at every node:

everything in the left subtree is smaller, everything in the right subtree is bigger (or equal).

Each step throws away about half the remaining nodes, so a well-shaped BST with n nodes needs about log₂ n steps: 20 steps for a million, because 2²⁰ ≈ 1,000,000. That's O(log n).

function insert(root, value) {
  if (root === null) return { value, left: null, right: null };
  if (value < root.value) root.left = insert(root.left, value);
  else root.right = insert(root.right, value);
  return root;
}
function search(root, value) {
  let steps = 0;
  let cur = root;
  while (cur !== null) {
    steps++;
    if (value === cur.value) return `found in ${steps} steps`;
    cur = value < cur.value ? cur.left : cur.right;
  }
  return `not found after ${steps} steps`;
}
let root = null;
for (const roll of [50, 30, 70, 20, 40, 60, 80]) root = insert(root, roll);
console.log(search(root, 60));
console.log(search(root, 65));

Output:

found in 3 steps
not found after 3 steps

The tree it built:

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80

insert is recursive (base case: an empty spot, null, becomes the new node). search is a loop: at each node go left or right. 65 would have to be to the right of 60 (50 → right to 70 → left to 60 → right), and that spot is empty, so after 3 steps we know it's not in the tree.

Sorted input breaks it

const rolls = Array.from({ length: 5000 }, (_, i) => i + 1);
let sorted = null;
for (const r of rolls) sorted = insert(sorted, r);
for (let i = rolls.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [rolls[i], rolls[j]] = [rolls[j], rolls[i]];
}
let mixed = null;
for (const r of rolls) mixed = insert(mixed, r);
console.log("mixed order: ", search(mixed, 5000));
console.log("sorted order:", search(sorted, 5000));

(with insert and search from above). Output (the mixed number changes with the shuffle, usually around 10 to 15):

mixed order:  found in 10 steps
sorted order: found in 5000 steps

The loop in the middle is a Fisher-Yates shuffle: it swaps each position with a random earlier one. Why sorted input is slow: every new roll is bigger than everything already in the tree, so it always goes right. The tree becomes one long line: a linked list in disguise, O(n) search. (With far more sorted values the recursive insert would also run out of call stack: RangeError: Maximum call stack size exceeded.)

The fix: build from the middle

function build(sorted, lo = 0, hi = sorted.length - 1) {
  if (lo > hi) return null;
  const mid = Math.floor((lo + hi) / 2);
  return { value: sorted[mid], left: build(sorted, lo, mid - 1), right: build(sorted, mid + 1, hi) };
}
const rolls = Array.from({ length: 1000000 }, (_, i) => i + 1);
const root = build(rolls);
console.log("root:", root.value);
console.log(search(root, 1000000));
console.log(search(root, 1));
console.log(search(root, 1000001));

Output:

root: 500000
found in 20 steps
found in 19 steps
not found after 20 steps

The middle value becomes the root, the left half builds the left subtree, the right half the right subtree. Every level halves the range, so the height is about log₂ n: a balanced tree. Libraries keep trees balanced while you insert, using self-balancing designs such as AVL trees and red-black trees.

BST shape Height search / insert
balanced about log₂ n O(log n)
random insert order average depth about 1.4 × log₂ n O(log n) on average
sorted insert order (a line) n O(n)

In-order traversal (left subtree, node, right subtree) of a BST visits the values in sorted order:

function inOrder(node, out = []) {
  if (node === null) return out;
  inOrder(node.left, out);
  out.push(node.value);
  inOrder(node.right, out);
  return out;
}

For the 7-roll tree above this gives [ 20, 30, 40, 50, 60, 70, 80 ].

Graphs: the city metro

On the metro map In a graph
a station a vertex (node)
a track between two stations an edge
riding out and coming back another way a cycle
each station's board: "next stations from here" an adjacency list

A graph is vertices joined by edges, with no root and with cycles allowed. A tree is a special graph with no cycles. Edges can be undirected (a track goes both ways, as here) or directed (a one-way street, a "follows" on social media), and weighted (minutes per ride) or not.

const metro = new Map([
  ["Home", ["Market", "Park"]],
  ["Market", ["Home", "Mall", "Station"]],
  ["Park", ["Home", "Office"]],
  ["Mall", ["Market", "Office"]],
  ["Station", ["Market"]],
  ["Office", ["Park", "Mall"]],
]);
 Station --- Market --- Home
               |          |
              Mall       Park
               |          |
             Office ------+

Each undirected track appears twice: Home lists Market and Market lists Home.

Walking it like a tree: the crash

function findRoute(from, to) {
  if (from === to) return [to];
  for (const next of metro.get(from)) {
    const rest = findRoute(next, to);
    if (rest) return [from, ...rest];
  }
  return null;
}
console.log(metro.get("Market"));
console.log(findRoute("Home", "Office"));

Output:

[ 'Home', 'Mall', 'Station' ]
main.js:10
  if (from === to) return [to];
  ^

RangeError: Maximum call stack size exceeded
    at findRoute (main.js:10:3)
    at findRoute (main.js:12:18)
    at findRoute (main.js:12:18)
    ...

Why: Home → Market → (Market's first neighbour) Home → Market → ... forever. Each call waits for the next, until JavaScript runs out of space on the call stack. Trees end at leaves; graphs have cycles.

Depth-first search (DFS) with a visited set

Like chalk marks in a maze: mark every station when you arrive, never enter a marked one again.

function findRoute(from, to, visited = new Set()) {
  if (from === to) return [to];
  visited.add(from);
  for (const next of metro.get(from)) {
    if (visited.has(next)) continue;
    const rest = findRoute(next, to, visited);
    if (rest) return [from, ...rest];
  }
  return null;
}
console.log(findRoute("Home", "Office").join(" -> "));

Output:

Home -> Market -> Mall -> Office

This is depth-first search: go as deep as possible along one path, back up only when stuck. It finds a route, the first one it stumbles on: 3 rides. But Home → Park → Office is only 2.

Breadth-first search (BFS) with a queue: the fewest stops

Ripples in a pond: explore everything 1 ride away, then everything 2 rides away, and so on. The first time you reach the target, no shorter route can exist. Stations discovered first are explored first: first in, first out, a queue (episode 34, with a head pointer).

function fewestStops(from, to) {
  const queue = [[from]];
  let head = 0;
  const visited = new Set([from]);
  while (head < queue.length) {
    const path = queue[head++];
    const last = path[path.length - 1];
    if (last === to) return path;
    for (const next of metro.get(last)) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push([...path, next]);
      }
    }
  }
  return null;
}
console.log(fewestStops("Home", "Office").join(" -> "));
console.log(fewestStops("Station", "Park").join(" -> "));

Output:

Home -> Park -> Office
Station -> Market -> Home -> Park
Ring Queue contents (routes)
0 [Home]
1 [Home, Market], [Home, Park]
2 [Home, Market, Mall], [Home, Market, Station], [Home, Park, Office] ← target

A station is marked when it's added to the queue, not when it's taken out, so it can never be queued twice. Complexity: every vertex is queued once and every edge checked once: O(V + E), where V is the number of vertices and E the number of edges. (Storing whole paths costs extra memory; a cheaper version stores each station's parent in a Map and rebuilds the path at the end.)

DFS vs BFS

DFS BFS
order one path to the end, then back up ring by ring
uses recursion (the call stack) or an explicit stack a queue
finds a path the path with the fewest edges
good for folders, mazes, "is there any way?", cycle detection fewest stops, nearest friend-of-friend, levels
time O(V + E) O(V + E)

For routes with different ride times (weighted edges), BFS isn't enough: that needs Dijkstra's algorithm, which comes later with priority queues.

Common mistakes (and what really happens)

Mistake What you see Why Fix
one loop over children Total files: 15 (really 24) a loop sees one level recursion on each child
a recursive function with no base case RangeError: Maximum call stack size exceeded it calls itself forever stop at a leaf / null
inserting sorted data into a BST 5,000 steps instead of about 10 the tree becomes a line build from the middle, or a self-balancing tree
walking a graph without visited RangeError: Maximum call stack size exceeded cycles: Home → Market → Home a visited Set
marking visited when dequeued in BFS the same station is queued many times it was added before being marked mark when you enqueue
DFS for the fewest stops Home -> Market -> Mall -> Office DFS returns the first route BFS with a queue
queue.shift() in BFS on a big graph slow on big graphs shift is O(n) a head pointer

Mini project: the metro planner

Count the stations reachable from a station (an explicit-stack DFS, no recursion), add a new track, and recompute the fewest stops. A Depot with no tracks shows what "unreachable" looks like.

const metro = new Map([
  ["Home", ["Market", "Park"]],
  ["Market", ["Home", "Mall", "Station"]],
  ["Park", ["Home", "Office"]],
  ["Mall", ["Market", "Office"]],
  ["Station", ["Market"]],
  ["Office", ["Park", "Mall"]],
  ["Depot", []],
]);
function reachable(start) {
  const visited = new Set([start]);
  const stack = [start];
  while (stack.length > 0) {
    const s = stack.pop();
    for (const next of metro.get(s)) {
      if (!visited.has(next)) {
        visited.add(next);
        stack.push(next);
      }
    }
  }
  return visited;
}
console.log(reachable("Home").size, [...reachable("Home")]);
console.log(reachable("Depot").size);
function addTrack(a, b) {
  metro.get(a).push(b);
  metro.get(b).push(a);
}
// fewestStops exactly as above
console.log(fewestStops("Station", "Office").join(" -> "));
addTrack("Station", "Office");
console.log(fewestStops("Station", "Office").join(" -> "));
console.log(fewestStops("Home", "Depot"));

Output:

6 [ 'Home', 'Market', 'Park', 'Office', 'Mall', 'Station' ]
1
Station -> Market -> Mall -> Office
Station -> Office
null

The new track cut Station → Office from 3 rides to 1. null means the Depot can't be reached from Home: the graph has two connected components.

Practice

1. Find the folder with the most files of its own in Neha's laptop.

Solution
function biggest(folder) {
  let best = folder;
  for (const child of folder.children) {
    const b = biggest(child);
    if (b.files > best.files) best = b;
  }
  return best;
}
console.log(biggest(laptop).name);

Output:

Photos

Same shape as countFiles: ask each child for its answer, then combine.

2. Write min(root) and max(root) for a BST.

Solution
function min(root) {
  let cur = root;
  while (cur.left !== null) cur = cur.left;
  return cur.value;
}
function max(root) {
  let cur = root;
  while (cur.right !== null) cur = cur.right;
  return cur.value;
}
console.log(min(root), max(root));

Output (for the 7-roll tree):

20 80

The smallest value is as far left as you can go, the biggest as far right. O(height).

3. Without running it: in which order does BFS from Home first discover the six stations?

Solution

Home, then ring 1: Market, Park; then ring 2: Mall, Station (from Market), Office (from Park). Mall and Station come before Office because Market was queued before Park.

Quick quiz

function depth(node) {
  if (node === null) return 0;
  return 1 + Math.max(depth(node.left),
                      depth(node.right));
}
// tree: 50 → left 30 → left 20
//          → right 70
console.log(depth(tree));

A. 2 B. 3 C. 4 D. 1

Answer

B: 3. The longest path is 50 → 30 → 20, three levels. The null children return 0 (the base case). Built with insert from 50, 30, 70, 20, it really prints 3.

Interview questions

  1. What is the difference between a tree and a graph? A tree is a connected graph with no cycles and a root; every node except the root has exactly one parent. A graph allows cycles, any number of connections, and no root.
  2. What is the time complexity of search in a BST? O(h), where h is the height: O(log n) if balanced, O(n) in the worst case (sorted inserts).
  3. What does in-order traversal of a BST give? The values in sorted order.
  4. Why does BFS find the shortest path in an unweighted graph? It explores all vertices at distance 1, then 2, and so on, so the first time it reaches the target, no shorter path exists.
  5. When would you use DFS instead of BFS? To check whether any path exists, to explore every reachable node with little memory on a wide graph, to detect cycles, or for topological sorting.
  6. How do you avoid infinite loops when traversing a graph? Keep a visited set and skip vertices already in it.
  7. How would you represent a graph in JavaScript? An adjacency list: a Map from each vertex to an array (or Set) of neighbours. An adjacency matrix (an n × n grid of 0/1) is an alternative for dense graphs.
  8. What are the two parts every recursive function needs? A base case that stops, and a recursive case that moves towards it.

Glossary

Term Meaning Example
tree nodes with children, a single root, no cycles Neha's folders
root the top node of a tree Documents
child / parent a node directly below / above another College / Documents
leaf a node with no children Sem1
subtree a node and everything below it College's subtree
depth levels from the root to a node Sem1: depth 2
height levels on the longest root-to-leaf path 3
recursion a function that calls itself on a smaller part countFiles(child)
base case where recursion stops if (node === null) return 0
call stack where waiting function calls are kept the lines in a RangeError trace
binary tree each node has at most a left and a right child { value, left, right }
binary search tree (BST) left subtree smaller, right subtree bigger, at every node 50 with 30 left, 70 right
O(log n) steps grow with the number of halvings 20 steps for a million
balanced tree height about log₂ n build from the middle
AVL / red-black tree BSTs that rebalance themselves on insert used inside libraries
in-order traversal left, node, right gives sorted values
Fisher-Yates shuffle swap each position with a random earlier one shuffling rolls
graph vertices joined by edges, cycles allowed the metro
vertex a node of a graph a station
edge a link between two vertices a track
cycle a path that returns to where it started Home → Market → Mall → Office → Park → Home
directed / undirected one-way / two-way edges one-way street / metro track
weighted edges carry a cost minutes per ride
adjacency list each vertex mapped to its neighbours metro.get("Home")
visited set vertices already seen new Set()
DFS depth-first search: go deep, then back up findRoute
BFS breadth-first search: ring by ring, with a queue fewestStops
O(V + E) time proportional to vertices plus edges BFS, DFS
connected component a group of vertices reachable from each other the Depot on its own
RangeError: Maximum call stack size exceeded too many nested calls recursion with no end

Summary

  • A tree is nodes with children: a root at the top, leaves at the bottom, no cycles.
  • Recursion answers "the same question on a smaller piece"; it needs a base case. One loop only sees one level.
  • A BST keeps smaller values left and bigger right: O(log n) search when balanced, O(n) when sorted inserts turn it into a line. Build from the middle, or use a self-balancing tree.
  • A graph has vertices, edges and cycles; store it as an adjacency list. Always keep a visited set.
  • DFS (recursion or a stack) finds a route; BFS (a queue) finds the route with the fewest edges. Both are O(V + E).
  • Next: sorting and searching, how sort really works and why sorted data is so useful.