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:
- a base case, where it stops without calling itself (here: a leaf, whose loop has nothing to visit), and
- 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
- 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.
- 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).
- What does in-order traversal of a BST give? The values in sorted order.
- 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.
- 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.
- How do you avoid infinite loops when traversing a graph? Keep a visited set and skip vertices already in it.
- How would you represent a graph in JavaScript? An adjacency list: a
Mapfrom 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. - 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
sortreally works and why sorted data is so useful.