What a tree is
You're keeping a set of values that must stay searchable — "is
7 in here?", "what's the next-biggest after 5?" — while you constantly insert and delete. A sorted array searches in O(log n) but inserts in O(n) (everything shifts); a linked list inserts in O(1) but can't binary-search. You want both fast — and a flat sequence can't give it.A binary tree breaks the deadlock by branching: each node has up to two children, a
left and a right, and one node at the top is the root. Make it a binary search tree (BST) with one invariant at every node: everything in the left subtree is smaller, everything in the right is larger.Now searching is binary search made physical — compare at a node and step left or right, discarding half the tree each step. Trees also naturally encode hierarchy: file systems, org charts, comment threads.
8
3
10
1
6
∅
14
Quick check
In a binary search tree, values SMALLER than a node live…
Answer it in the interactive lesson to keep your progress.
The core operations
A node is
{ val, left, right }, with each child either another node or null, and you hold a reference to the root. The moves:- search — compare the target to the node; go
leftif smaller,rightif larger, until you match or hitnull. - insert — the same walk, then attach the new node where you fell off the tree.
- traverse — visit every node; almost every tree operation is a small recursion: do something with the node, then recurse into
leftand/orright.
Here's how you reach into the example tree:
const sample = buildTree([8, 3, 10, 1, 6, null, 14]);
console.log(sample.val); // 8 (the root)
console.log(sample.left.val, sample.right.val); // 3 10
console.log(treeToArray(sample)); // [8, 3, 10, 1, 6, null, 14]Quick check
Searching for 7 in a BST whose root is 5: predict the first step.
Answer it in the interactive lesson to keep your progress.
Your first tree problem: in-order traversal
A traversal visits every node of a tree once. We'll do an in-order traversal (left, node, right), which has a lovely property on a search tree: it visits the values in sorted order. For a small tree with root
5 and children 3 (left) and 8 (right), in-order visits 3, 5, 8.The steps
To traverse a node in-order:
- If the node is
null, stop — nothing to visit (the base case). - Recurse into the left child first (the smaller values).
- Record this node's value.
- Recurse into the right child (the larger values).
The recursion naturally gives left-subtree → node → right-subtree at every level. In the animation, watch the visit order light up: the walk dives all the way left first, and a node is only recorded once its whole left side is done. Before each step, predict which node gets recorded next — on a search tree your predictions should come out in sorted order. In JavaScript, one way to write those steps:
This section has a step-by-step animation in the interactive lesson.
const tree = buildTree([8, 3, 10, 1, 6, null, 14]);
function inorderVals(node, acc) {
if (!node) return acc; // base case: nothing to do
inorderVals(node.left, acc); // smaller values first
acc.push(node.val); // then this node
inorderVals(node.right, acc);// then larger values
return acc;
}
console.log(inorderVals(tree, [])); // [1, 3, 6, 8, 10, 14]Quick check
In-order traversal of a binary SEARCH tree visits values…
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- An unbalanced tree is just a list. Insert already-sorted values into a plain BST and it degrades into a straight line — search back to
O(n). Real systems use self-balancing trees (AVL, red-black) to prevent this. - Missing the null base case. Recursing into a
nullchild and reading.valthrows. Every tree recursion needs anif (node === null) returnguard. - Confusing traversals. In-order, pre-order, post-order, and level-order visit in different sequences — pick the one the problem needs.
Quick check
Tree recursion always starts with `if (!node) return …` because…
Answer it in the interactive lesson to keep your progress.
Take it further — level-order (breadth-first)
In-order used recursion (a stack under the hood). To visit a tree top-to-bottom, left-to-right instead, swap the stack for a queue — that's breadth-first search. Dequeue a node, record it, enqueue its children, repeat. Each wave of the queue is one level of the tree:
function levelOrder(root) {
const out = [];
const queue = [root];
while (queue.length) {
const node = queue.shift(); // take the front
if (!node) continue;
out.push(node.val);
queue.push(node.left, node.right); // children join the back
}
return out;
}
console.log(levelOrder(buildTree([8, 3, 10, 1, 6, null, 14]))); // [8, 3, 10, 1, 6, 14]Quick check
Level-order on root 5, children 3 and 8, and 3 has a child 1. Predict the visit order.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, when the tree stays balanced, its height is about
log n, and the costs follow:| Operation | Balanced | Unbalanced (worst) |
|---|---|---|
| search / insert / delete | O(log n) | O(n) — the tree is a list |
| traverse every node | O(n) | O(n) |
| recursion stack | O(log n) height | O(n) |
The catch: an unbalanced tree (e.g. sorted inserts) degrades to a list, and everything becomes
O(n) — which is why real systems self-balance.Key takeaways:
- A BST keeps
left < node < right, so search halves the tree each step. - Balanced →
O(log n)search/insert; unbalanced →O(n). - Tree work is recursion; every path bottoms out at a
nullbase case.
This stores hierarchy while keeping search and insert fast. These classics each get their own lesson later (no need to know them yet): validate a BST / lowest common ancestor (reason with the invariant), level-order traversal (breadth-first with a queue), and max depth / balanced tree / path sum (one clean recursion each). Next up in order: Binary Search Trees — one ordering promise that turns every tree walk into a binary search.