"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. A two-way shape suits yes/no decisions, binary search trees, and heaps, but two children alone do not halve a search space. Logarithmic search needs additional invariants such as key ordering and balance. General and binary trees can both model hierarchy or decisions; the useful meaning comes from the problem-specific invariant.
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, generally good 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. That shape can support decisions, binary-search-tree ordering, and heaps, but logarithmic search comes from additional ordering and balance invariants. 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 I saw why two-way structure is useful—but Dad added the guardrail: two children do not automatically discard half the possibilities. Binary search gets that power from ordering and balance, while heaps impose a different invariant. The fork is a shape; the invariant gives it meaning.
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.