"Restrict each node to two children and something magical happens: every node becomes a yes/no fork. That single constraint is the seed of binary search, heaps, and half the structures in computing."
The Constraint That Unlocks Everything
A binary tree is a tree where every node has at most two children, conventionally called left and right. Why is "two" so special? Because two children is a binary decision — left or right, smaller or larger, yes or no — and a chain of binary decisions is exactly how you halve a search space. The two-way fork is the structural seed of binary search (Searching track), heaps (next track), and the decision trees behind machine learning. General trees model hierarchy; binary trees model decisions.
A Vocabulary of Shapes
You'll hear these adjectives; they describe how 'filled in' a binary tree is:
Full — every node has either 0 or 2 children (never just 1).
Complete — every level is filled except possibly the last, which fills left to right. (This is the shape heaps use.)
Perfect — every level completely full; a perfect triangle.
Balanced — the height stays around log n, so operations stay O(log n). This is the property the whole track is chasing.
Two Ways to Store One
You can represent a binary tree two ways, and the choice previews the next track:
Linked nodes — each node object holds left and right references. Flexible, works for any shape, the default.
An array — for a complete tree, you can skip pointers entirely and store nodes in an array, using index math: the children of index i live at 2i+1 and 2i+2, and the parent at (i−1)//2. No pointers, perfect cache locality. This is exactly how a heap is built — remember this formula; you'll meet it again in two lessons.
A binary tree caps children at two, turning every node into a yes/no fork — the seed of binary search and heaps. Store it with linked left/right nodes, or (for complete trees) in an array where index i's children are 2i+1 and 2i+2.
Why Height Is Everything
A binary tree with n nodes can be as short as about log₂(n) (if bushy and balanced) or as tall as n (if it degenerates into a one-child-per-node chain). Since most tree operations cost is proportional to the height, that range — log n versus n — is the entire difference between a fast tree and a slow one. Keeping the height near log n is the obsession that drives balanced trees, three lessons from now.
Pippa's Confession
I assumed "binary" tree was just an arbitrary rule — why two and not three? Dad reframed it as a decision: "Two children is one question. Left or right. Less or more." Suddenly binary trees weren't a limitation but a machine for halving — every node a fork in the road that discards half the possibilities. That reframe is what connected binary trees to binary search in my head; they're the same idea wearing different clothes.
Code
Linked nodes and the array index trick·python
class BinaryNode:
"""The binary tree node everyone uses: a value, a left, a right."""
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
# 4
# / \
# 2 6
# / \
root = BinaryNode(4, BinaryNode(2, BinaryNode(1), BinaryNode(3)), BinaryNode(6))
def height(node):
if node is None:
return -1 # empty subtree: height -1, a leaf: 0
return 1 + max(height(node.left), height(node.right))
print("height:", height(root)) # 2
# ARRAY representation of a COMPLETE binary tree (no pointers!):
# parent of i = (i-1)//2 ; children of i = 2i+1, 2i+2.
arr = [4, 2, 6, 1, 3] # same tree, level by level
def children(i):
return (2 * i + 1, 2 * i + 2)
print("children of index 0 (value 4):", [arr[j] for j in children(0)]) # [2, 6]
print("children of index 1 (value 2):", [arr[j] for j in children(1)]) # [1, 3]
# Remember this index math — it's exactly how heaps work (two lessons ahead).
You have 7 nodes to arrange into a binary tree. What's the minimum possible height (bushiest arrangement) and the maximum possible height (most lopsided)? Then explain why most tree operations care about height, and what that implies about which of those two shapes you'd want in practice.
Hint
Min height: a perfect tree of 7 nodes is height 2 (levels of 1, 2, 4). Max height: a one-sided chain is height 6. Operations walk from root toward a leaf, so cost ~ height; you want the bushy log-n shape, not the n-tall chain.
Progress
Progress is local-only — sign in to sync across devices.