Trees
A tree is a data structure for things that branch: a hierarchy. A file system,
a family tree, an organisation chart, the tags of a web page — all are trees. Unlike a
linked list, where
each node points to just one "next", a tree node can point to several children,
so the structure fans out from a single starting point.
Every tree has exactly one root (the top node, with no parent). Each node may
have children below it; a node with no children is a leaf. Any
node together with everything beneath it is itself a smaller tree — a subtree —
which is why trees are so naturally recursive.
The vocabulary
- Root — the single node at the top; the only node with no parent.
- Parent / child — a node directly above / below another, joined by an edge.
- Leaf — a node with no children (the tips of the tree).
- Subtree — a node and all of its descendants.
- Depth of a node — how many edges lie between it and the root (the root has
depth 0).
- Height of the tree — the depth of its deepest leaf.
A binary tree is the common special case where every node has at most
two children (a "left" and a "right"). Ordering those children by value gives a
binary search
tree, and visiting every node in order is the job of the
tree traversals.
A tree in code
A node holds a value and a list of its children. Because a subtree is just a smaller tree, the
natural way to measure a tree is recursion: a function that calls itself on each
child. Here we count the nodes and find the height of a little tree — press Run:
interface TreeNode {
value: string;
children: TreeNode[];
}
// A small tree: A
// / | \
// B C D
// / \ \
// E F G
const tree: TreeNode = {
value: "A",
children: [
{ value: "B", children: [
{ value: "E", children: [] },
{ value: "F", children: [] },
] },
{ value: "C", children: [] },
{ value: "D", children: [
{ value: "G", children: [] },
] },
],
};
function countNodes(n: TreeNode): number {
// 1 for this node, plus the nodes in every child's subtree.
let total = 1;
for (const child of n.children) total += countNodes(child);
return total;
}
function height(n: TreeNode): number {
// A leaf has height 0; otherwise 1 + the tallest child subtree.
if (n.children.length === 0) return 0;
let tallest = 0;
for (const child of n.children) tallest = Math.max(tallest, height(child));
return 1 + tallest;
}
console.log("nodes =", countNodes(tree)); // 7
console.log("height =", height(tree)); // 2
console.log("edges =", countNodes(tree) - 1); // always nodes - 1
Notice the last line: a tree with N nodes always has exactly
N - 1 edges, because every node except the root is joined to the tree
by precisely one edge — the one to its parent.
Trees are a special kind of graph
A tree is really a graph
with two extra promises: it is connected (you can reach every node from the root)
and it has no cycles (you can never loop back to where you started). Those two
promises force a lovely property:
- A tree is a connected, acyclic graph with a chosen root.
- There is exactly one path between any two nodes.
- A tree of N nodes has exactly N - 1 edges.
The folders on your computer are a tree: one root drive, folders inside folders, files as the
leaves. A web page is a tree — the DOM — with <html> at the
root and every tag nested inside its parent. A knockout tournament bracket is a (binary) tree
read from the leaves up. Once you spot the branching shape, you see trees everywhere.
-
The root has no parent, and a leaf has no children — don't
look for either. Every other node has exactly one parent.
-
Add an edge that joins two existing nodes and you create a cycle — and it is
no longer a tree, it's a general graph. "Tree" is the promise of *no* loops.
-
Depth is measured from the root down to a node; height is
measured from the deepest leaf up. They're easy to swap by accident.