Some data is naturally linear — a list of scores, a queue of jobs. But a great deal of the world is not. A file system branches into folders that branch into more folders. A company branches into teams. A web page branches into elements that contain yet more elements. None of these fits a straight line; they are trees, and they describe anything with a hierarchy.
Then there are the things that connect back on themselves: friends who know friends, flights between cities, dependencies between modules. These are graphs — collections of nodes joined by edges, with no strict top or bottom. Trees and graphs are the two structures that model real relationships, and the skills that traverse them, recursion for depth and queues for breadth, are among the most reusable in programming.
flowchart TD R["root: A"] --> B["leaf: B"] R --> C["C"] C --> D["leaf: D"] style R fill:#3776ab,color:#fff style B fill:#1e7f3d,color:#fff style D fill:#1e7f3d,color:#fff
Representing a tree
A tree node is an object holding a value and a list of its children. The single node with no parent is the root; a node with no children is a leaf. Because every node has the same shape, a tree is a recursive structure: the whole is a node whose children are themselves smaller trees.
That self-similarity is why recursion fits trees so perfectly. To do something to every node, you handle the current node and then apply the same logic to each child. There is no loop counter to manage and no risk of skipping a branch — the recursion descends every path for you. A tree of ten thousand nodes is traversed by the same few lines that traverse a tree of three.
function makeNode(value, children = []) {
return { value, children };
}
const root = makeNode('root', [
makeNode('a'),
makeNode('b', [makeNode('c')])
]);
function walk(node) {
console.log(node.value);
for (const child of node.children) walk(child);
}
walk(root);
Two ways to walk a structure
There are two fundamental traversals, and they answer different questions. Depth-first search dives all the way down one branch before backing up — implemented with recursion, or an explicit stack. It is the natural choice for summing every value, finding the deepest path, or copying a tree. Breadth-first search visits every node at the current depth before moving deeper — implemented with a queue. It is how you find the shortest path in an unweighted graph or process a tree level by level.
The difference is the order in which nodes are visited, not which nodes are visited. Depth-first reaches deep quickly; breadth-first stays shallow and broad. Pick by the question you are asking: depth-first when the answer lies down a single branch, breadth-first when it sits at the shallowest reachable layer.
flowchart LR D["depth-first<br/>dives down one branch<br/>before backing up"] --> S["uses a stack<br/>or recursion"] F["breadth-first<br/>visits a whole depth<br/>before going deeper"] --> Q["uses a queue"] style D fill:#e0900b,color:#fff style F fill:#3776ab,color:#fff
function treeSum(node) {
if (!node) return 0;
let total = node.value;
for (const child of node.children) {
total += treeSum(child);
}
return total;
}
const t = {
value: 1,
children: [
{ value: 2, children: [] },
{ value: 3, children: [{ value: 4, children: [] }] }
]
};
console.log(treeSum(t));
Graphs: nodes and edges
A graph drops the idea of a root entirely. It is a set of nodes connected by edges, and any node can link to any other. The common representation is an adjacency list: a Map, or a plain object, mapping each node to the array of its neighbours. To traverse a graph you still use depth-first or breadth-first search, but there is a new hazard a tree does not have — cycles. In a tree every path eventually ends at a leaf, so recursion always terminates. In a graph an edge can point back to a node you already visited, and a naive traversal will chase that loop forever.
The defence is a visited set: before processing a node, record it, and never process the same node twice. With that one addition, the same search code that walks a tree walks a graph safely, and a queue-driven breadth-first search finds the shortest hop-count between any two nodes.
flowchart LR A["A"] --> B["B"] A --> C["C"] B --> D["D"] C --> D D -.-> A style A fill:#3776ab,color:#fff
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const neighbor of graph[node] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return order;
}
const graph = {
A: ['B', 'C'],
B: ['D'],
C: ['D'],
D: []
};
console.log(bfs(graph, 'A'));
What does this print? preOrder logs a node's value, then recurses into each child left to right. Trace it by hand.
function preOrder(node) {
if (!node) return;
console.log(node.value);
for (const child of node.children) {
preOrder(child);
}
}
const tree = {
value: 'A',
children: [
{ value: 'B', children: [] },
{ value: 'C', children: [
{ value: 'D', children: [] }
] }
]
};
preOrder(tree);
preOrder logs the current node first, then visits its children in order.
A is logged, then B, then C, and finally D under C.
Each value prints on its own line.
Write countNodes(node) that returns the total number of nodes in the tree rooted at node, including the root itself. Return 0 if node is null.
function countNodes(node) {
// count this node plus every descendant
}
A null node contributes 0; any real node contributes 1 for itself.
Add countNodes(child) for each child to the running total.
Return the total after the loop.
function countNodes(node) {
if (!node) return 0;
let total = 1;
for (const child of node.children) {
total += countNodes(child);
}
return total;
}
This reachability check works on a tree but recurses forever on a graph that has a cycle, because it never remembers which nodes it has already visited. Add a visited set so the search terminates and still returns the right answer.
function canReach(graph, start, target) {
if (start === target) return true;
for (const neighbor of graph[start] || []) {
if (canReach(graph, neighbor, target)) return true;
}
return false;
}
Add a visited parameter defaulting to new Set() so the top call starts fresh.
If visited already has the current node, return false at once.
Add the current node to visited before you recurse into its neighbours, and pass visited along.
function canReach(graph, start, target, visited = new Set()) {
if (start === target) return true;
if (visited.has(start)) return false;
visited.add(start);
for (const neighbor of graph[start] || []) {
if (canReach(graph, neighbor, target, visited)) return true;
}
return false;
}
Which data structure does breadth-first search use to pick the next node to visit?
BFS explores nodes in the order they were discovered, so it uses a queue: the first node enqueued is the first one explored, which keeps the traversal level by level.
Write treeHeight(node) that returns the height of the tree — the number of nodes on the longest path from the root down to a leaf. A single leaf node has height 1, and a null node has height 0.
function treeHeight(node) {
// return the height of the tree
}
A null node has height 0; any real node is at least height 1.
Find the tallest child by tracking the maximum of treeHeight(child).
Return 1 plus that maximum.
function treeHeight(node) {
if (!node) return 0;
let max = 0;
for (const child of node.children) {
const h = treeHeight(child);
if (h > max) max = h;
}
return 1 + max;
}
Recap
- A tree is a recursive structure: a node with a value and a list of child trees; one root, many leaves.
- Depth-first search uses recursion, or a stack, and dives down one branch at a time.
- Breadth-first search uses a queue and visits a whole depth before going deeper.
- A graph is nodes plus edges; represent it with an adjacency list.
- Graphs can contain cycles, so always carry a visited set to keep traversals finite.
That completes your tour of the core data structures. The course project ahead asks you to combine arrays, maps, and a little recursion into one small working tool.