The words
The height is what every complexity in the next three lessons is expressed in. A balanced tree of n nodes has height log n; a degenerate one has height n and is a linked list wearing a costume. Almost all of tree engineering is about keeping that from happening.
You already use trees constantly: the DOM, a filesystem, JSON, an abstract syntax tree, a database index, the decision tree in a routing table.
| Term | Means |
|---|---|
| Root | The one node with no parent |
| Leaf | A node with no children |
| Height | The longest path from the root down to a leaf, counted in edges |
| Depth | How far one node is from the root |
| Binary tree | At most two children per node |
| Complete | Every level full except possibly the last, which fills left to right |
| Balanced | The two subtrees of every node differ in height by at most one |
The three depth-first orders
"Deleting a folder" is post-order and "printing a folder listing" is pre-order, and if you ever get them the wrong way round the operating system will tell you.
/* pre-order: node, left, right — the node BEFORE its children */
function preOrder(node, out = []) {
if (!node) return out;
out.push(node.value);
preOrder(node.left, out);
preOrder(node.right, out);
return out;
}
/* in-order: left, node, right — the node BETWEEN its subtrees */
/* post-order: left, right, node — the node AFTER its children */| Order | Use it for |
|---|---|
| Pre | Copying or serialising a tree — you need the node before you can place its children |
| In | A binary search tree: it comes out sorted |
| Post | Deleting, freeing, or evaluating an expression — you need the children’s results first |
Breadth first, level by level
The only traversal that is not naturally recursive, because it needs a queue rather than a stack. That single swap — queue instead of stack — is the entire difference between breadth-first and depth-first, and it comes back in the graph lessons unchanged.
Level order is what you want for "the shallowest node that…", for printing a tree by rows, and for anything where nearer means better.
function levelOrder(root) {
const out = [];
const queue = [root];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
if (!node) continue;
out.push(node.value);
queue.push(node.left, node.right);
}
return out;
}Depth, and the shape it implies
Notice how short these are. A tree is a recursive shape, so recursion over it is usually one line plus a null check — which is exactly the case where recursion is the right tool rather than the clever one.
That isBalanced is O(n²) because it recomputes the height at every node. Returning the height and the verdict together makes it O(n), and doing so is a good exercise.
const height = (node) => (node ? 1 + Math.max(height(node.left), height(node.right)) : 0);
const size = (node) => (node ? 1 + size(node.left) + size(node.right) : 0);
const isBalanced = (node) => {
if (!node) return true;
return Math.abs(height(node.left) - height(node.right)) <= 1
&& isBalanced(node.left) && isBalanced(node.right);
};Traversing without recursion
Push right before left, because a stack reverses. This version survives a tree deep enough to overflow the call stack — which a degenerate tree of a million nodes certainly is.
function preOrderIterative(root) {
const out = [];
const stack = [root];
while (stack.length) {
const node = stack.pop();
if (!node) continue;
out.push(node.value);
stack.push(node.right, node.left); // right first, so left comes off first
}
return out;
}