Algorithms from zero
The binary tree
You know that a linked list is a chain of nodes, each pointing to the next. Now imagine a structure where each node points not to one next node, but to two: a left child and a right child. This is a tree. Instead of a linear chain, you get a branching structure—one root node at the top, spreading downward into leaves. Trees let you organize hierarchies (like a file system), and they fit recursion so naturally that processing a tree feels like breathing.
After this lesson you can explain what a tree is, distinguish a binary tree from other trees, use the terminology (root, leaf, parent, child, depth, height, subtree, level), implement a node with left and right pointers, navigate a binary tree by following child pointers, and recognize when a tree is the right data structure.
What is a tree?
A tree is a hierarchy of nodes connected by edges. One node is special: the root, at the top. Every other node has exactly one parent (the node pointing to it). A node can have zero, one, or more children (nodes it points to).
Visual:
1 (root)
/ \
2 3
/ \
4 5Here, node 1 is the root. Node 2 is the parent of 4 and 5. Node 4 is a child of 2. Nodes 4 and 5 are siblings (they share the same parent).
What is a binary tree?
A binary tree is a tree where each node has at most 2 children. We call them the left child and the right child. A node can have:
- No children (a leaf)
- One child (left only, or right only)
- Two children (both left and right)
The binary tree above:
1
/ \
2 3
/ \
4 5Node 1 has a left child (2) and a right child (3). Node 2 has two children. Node 3 has none. Nodes 4 and 5 are leaves.
Tree terminology
- Root: The topmost node (no parent).
- Leaf: A node with no children.
- Internal node: A node with at least one child.
- Parent / Child: If node A points to node B, A is the parent and B is the child.
- Sibling: Two nodes with the same parent.
- Ancestor / Descendant: Node A is an ancestor of B if A is on the path from B up to the root. B is a descendant of A.
- Level: All nodes at the same distance from the root are at the same level. The root is at level 0.
Depth vs. Height (this trips everyone up)
- Depth of a node = the number of edges from the root down to that node. The root has depth 0.
- Height of a node = the number of edges from that node down to its furthest leaf descendant. A leaf has height 0.
- Height of the tree = the height of the root.
Memory aid: Depth is how deep you’ve gone down from the root. Height is how tall the subtree reaches below you.
Example:
1 (depth=0, height=2)
/ \
2 3 (depth=1, height=1 for node 2; height=0 for node 3)
/ \
4 5 (depth=2, height=0 for both)Node 4 has depth 2 (two edges from root: 1→2→4) and height 0 (no children). Node 2 has depth 1 and height 1 (one edge down to its furthest leaf).
Subtrees and recursion
A subtree is any node plus all its descendants. The left subtree of a node is the subtree rooted at its left child. The right subtree is rooted at its right child.
A binary tree is defined recursively:
- An empty tree is a binary tree.
- A tree with a root and a left subtree (which is a binary tree) and a right subtree (which is a binary tree) is a binary tree.
This recursive definition is the key insight: to process any tree, you process the root, then recursively process the left subtree, then the right subtree. This structure is why recursion and trees are meant for each other.
Representing a node in code
In a linked list, each node held a value and a pointer to the next node. In a binary tree, each node holds a value and pointers to the left and right children:
1
class Node {
2
constructor(value, left = null, right = null) {
3
this.value = value;
4
this.left = left;
5
this.right = right;
6
}
7
}
8
9
// Build the tree:
10
// 1
11
// / \
12
// 2 3
13
// / \
14
// 4 5
15
16
let node4 = new Node(4);
17
let node5 = new Node(5);
18
let node2 = new Node(2, node4, node5);
19
let node3 = new Node(3);
20
let root = new Node(1, node2, node3);
- L1 Node constructor stores value, left, and right.
- L7 Build bottom-up: leaves first.
- L13 Root is the entry point to the whole tree.
Navigating the tree by following pointers
To read the tree, you follow parent→child links. Each node is a step down:
1
// Access nodes by following left/right pointers
2
let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
3
4
// Navigate to the left child of root
5
let leftChild = root.left; // Node 2
6
7
// Navigate to the left child of node 2
8
let leftGrandchild = root.left.left; // Node 4
9
10
// Navigate to the right child of node 2
11
let rightGrandchild = root.left.right; // Node 5
12
13
// Each link is a single pointer hop
14
console.log(leftChild.value); // 2
15
console.log(leftGrandchild.value); // 4
- L5 root.left follows the left pointer from root.
- L8 root.left.left hops through two pointers.
- L11 root.left.right hops left then right.
- L14 Each navigation accesses the value property.
A simple helper: checking if a node is a leaf
A leaf has no children (both left and right are null). Here is a small helper function:
1
function isLeaf(node) {
2
return node.left === null && node.right === null;
3
}
4
5
let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
6
7
console.log(isLeaf(root.left.left)); // true (node 4 is a leaf)
8
console.log(isLeaf(root.left)); // false (node 2 has children)
9
console.log(isLeaf(root)); // false (root has children)
- L1 A leaf is a node with no children.
- L2 Check if both pointers are null.
- L6 Construct the tree.
- L8 Node 4 has no children, so isLeaf returns true.
1
let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
2
let target = root.left.right; // Navigate to node 5
3
console.log(target.value);
Time complexity
Building the tree from scratch (creating n nodes) takes O(n) time. Navigating the tree by following pointer hops (e.g., root.left.right) takes O(1) per hop. Following a path of length d takes O(d). The isLeaf helper is O(1).
Time = O(1) per pointer hop; O(n) to build the entire tree.
Space complexity
Space is used to store the tree structure: each of the n nodes occupies O(1) space. The tree itself uses O(n) space in memory.
Space = O(n) for the tree structure itself. Individual operations like isLeaf use O(1) extra space.
What is the depth of a node?
What is the height of a node?
What is the height of a leaf node?
In code, how do you represent a binary tree node?
What is the worst-case height of a binary tree with 7 nodes?
lesson.inset.undefined
Depth ≠ Height. Depth measures distance from the root down to you. Height measures distance from you down to the furthest leaf. They point in opposite directions.
lesson.inset.undefined
Empty tree. A tree can be empty (no nodes). The height of an empty tree is sometimes defined as -1, sometimes as 0, depending on convention. Always check the definition in your problem.
lesson.inset.undefined
Draw a tree. Draw a binary tree with 5 nodes. Label the root, leaves, and one internal node. Then calculate the depth and height of each node. This is the fastest way to cement the terminology.
Why is a tree a natural fit for recursive algorithms?
A tree is a hierarchy of nodes with one root at the top. A binary tree restricts each node to at most 2 children: left and right. Trees use terminology: root, leaf, parent, child, sibling, ancestor, descendant, level. Depth is the number of edges from the root down to a node; height is the number of edges from a node down to its furthest leaf. A subtree is a node plus all its descendants. In code, represent a node as { value, left, right }, where left and right are null if there is no child. Navigate a tree by following left and right pointers from the root. A leaf is any node where both left and right are null. Binary trees are the foundation for heaps, binary search trees, and many other algorithms. Next, you will learn traversals: how to visit every node in a specific order.