What is a tree?
A tree is a structure that stores values in a hierarchy — parent-and-child relationships — instead of in a flat line. It is built from nodes: one node at the top is the root, every node can have children below it, and a node with no children is called a leaf. A binary tree is simply a tree where each node has at most two children, called
left and right.In this lesson you'll learn the names for a tree's parts, how to reach into one with code, and the two fundamental ways to visit every node.
You already navigate trees every day: your computer's folders (a folder is the parent of the files and folders inside it), a company org chart (the CEO at the root, teams as subtrees), a comment thread (each reply is a child of the comment above it). Whenever data nests, a tree is its natural shape.
One signpost before we start: this lesson is about binary trees — the shape and how to walk it. Its famous cousin, the binary search tree (BST), adds an ordering rule on top of the same shape and gets its own lesson next. You don't need it today.
Read one org chart in words before watching it: the CEO sits at the top — the root, the single entry point. Directly below: Eng and Sales, the CEO's children (and the CEO is their parent). Below Eng sit Ana and Ben; below Sales, Cai — the leaves, with nobody under them. And here's the detail that powers everything later: Eng plus everyone under Eng is a complete little tree of its own. Watch the chart light up part by part below. (The coded traversals live in the See it step.)
This section has a step-by-step animation in the interactive lesson.
Quick check
In the org chart, which nodes are the LEAVES?
Answer it in the interactive lesson to keep your progress.
The core operations
In code, a node is
{ val, left, right } — its value plus up to two children, where each child is either another node or null (no child there). You hold a reference to the root; everything else is reached by stepping through children, exactly like following .next in a linked list, except now each step offers two directions.The moves every tree problem is built from:
- reach a node — step child by child from the root:
root.left,root.right.left, … - traverse — visit every node. Because each subtree is itself a tree, traversal is a natural recursion (the previous lesson!): do something with the node, then recurse into
leftandright. - measure — count nodes, find the height, sum the values: each is a tiny recursion that combines answers from the two children.
The figure shows the example tree the code below builds — here's how you reach into it. (
buildTree and treeToArray are helpers this course provides in every tree exercise: they convert between the level-order array shorthand and real linked nodes — the representation section below shows what buildTree does by hand.)Building a Tree in JavaScript
8
3
10
1
6
∅
14
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
In { val, left, right }, what does it mean when a node's left is null?
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 exactly once. We'll do an in-order traversal, which follows one rule at every node: left subtree first, then the node itself, then the right subtree. 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.
- Record this node's value.
- Recurse into the right child.
Trace it on the example tree
| step | where the walk is | recorded so far |
|---|---|---|
| 1 | dive left from 8 → 3 → 1 (1 has no left) | [1] |
| 2 | back up to 3, record it, then its right child 6 | [1, 3, 6] |
| 3 | 3's subtree done — record the root 8 | [1, 3, 6, 8] |
| 4 | into the right side: 10 (no left), then 14 | [1, 3, 6, 8, 10, 14] |
A node is only recorded once its entire left side is finished. And notice something curious: the values came out in sorted order. That's no accident — this tree happens to be arranged as a binary search tree, and the next lesson turns that little miracle into a superpower. (The See it step animates this walk node by node.)
In-Order Traversal in JavaScript
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. The four traversals differ only in WHEN each node is recorded relative to its children — but that tiny difference decides what the output is good for:
| traversal | order at each node | typical use |
|---|---|---|
| in-order | left → node → right | sorted output on a BST (this lesson) |
| pre-order | node → left → right | copying/serializing a tree — the root must come first |
| post-order | left → right → node | deleting or measuring — children must finish before the parent |
| level-order | whole levels, top to bottom | anything "by level" (the next section, with a queue) |
Pick the one the problem needs; the recursion skeleton is identical, only the
record line moves.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.
Level-Order Traversal in JavaScript
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, tree costs are set by two numbers:
n, the node count, and h, the tree's height (the longest root-to-leaf path). A balanced tree — branches of roughly equal depth — has height about log n; a lopsided one can have height n:| Operation | Balanced tree | Skewed tree (worst) |
|---|---|---|
| traverse every node | O(n) | O(n) |
| walk root → leaf | O(log n) | O(n) — the tree is a list |
| recursion stack while traversing | O(log n) | O(n) |
Traversal always touches everything (
O(n)) — no shape changes that. What the shape does change is the cost of any operation that walks one root-to-leaf path, which is exactly what the BST lesson exploits.Key takeaways:
- A tree stores hierarchy: root at the top, children below, leaves at the tips,
nullwhere a branch ends. - Tree work is recursion; every path bottoms out at a
nullbase case. - Height decides path costs: balanced ≈
log n, skewed ≈n.
The See it step animates the classics: build & traverse, level-order in waves, the diameter, and lowest common ancestor. These each get their own lesson or challenge later: max depth / balanced check / path sum (one clean recursion each) and level-order variants (queue-driven). Next up in order: Binary Search Trees — one ordering promise that turns every tree walk into a binary search.