What is a Binary Tree
A binary tree is a tree where every node has at most two children. That is the entire addition to the previous article — one number, changed from "any" to "two".
It buys more than it looks like. The two children get names, left and right, and because they are named they are no longer interchangeable: a node with only a left child is a different tree from a node with only a right child, even though both have one child. That asymmetry is what every later article in this series builds on.
Every twenty questions game is a binary tree. "Is it bigger than a car?" splits everything you might be thinking of into two groups, and the answer picks one. The next question splits that group again.
The reason the game works in twenty questions is the same reason binary trees matter: each answer discards half of what is left. Twenty halvings covers a million possibilities. That number — how many halvings you get before you run out of tree — is the height, and it is what this article is really about.
node 2 has both children; node 3 has only a right child, which is a different tree from having only a left one
The problem a general Tree couldn't solve
The general tree from the previous article can hold any hierarchy, and that flexibility costs it two things.
You cannot reason about its height. A tree with 100 nodes might have height 1 — a root with 99 children — or height 99. Knowing the node count tells you nothing about how far you might have to walk, and the height is the cost of every operation. Cap the children at two and the two numbers become linked: n nodes in a tidy binary tree means height about log₂ n, and that relationship is the entire reason the rest of this series exists.
You cannot put it in an array. A node with a variable number of children needs a slice per node, which means a separate heap allocation per node and pointer chasing to reach any of them. Fix the count at two and the positions become computable — a child's index is arithmetic on its parent's, so the whole tree collapses into one flat block of memory with no pointers at all. That trick is what makes the heap in the last article of this series fast, and it only works because of the two.
So the two-child limit is not a restriction the structure suffers. It is the thing that turns a tree from a container into something you can predict.
The shapes a Binary Tree can take
Most of the vocabulary around binary trees describes their shape, and it is worth being precise because the terms overlap in ways that trip people up. Every definition below is about the same question — where are the nodes allowed to be missing.
Full
A full binary tree is one where every node has either zero or two children. Never exactly one.
node 2 is a leaf, node 3 has both — and nothing in between
Note that this says nothing about where the leaves sit. A full tree can be wildly lopsided; it just cannot have a node with a lonely single child.
Complete
A complete binary tree has every level filled except possibly the last, and the last level fills from the left with no gaps.
six nodes, no gap before the end — and node 3 has one child, so this is not full
This is the shape that matters most in practice, because it is exactly the shape that fits an array with no wasted slots. Hold that thought until the array representation below.
Perfect
A perfect binary tree has every level completely filled. There are no gaps anywhere, which forces a very specific node count: a perfect tree of height h has exactly 2^(h+1) − 1 nodes.
height 2, so 2³ − 1 = 7 nodes, and no other count is possible
Perfect is the strongest of the three: a perfect tree is automatically complete and automatically full. The reverse fails in both directions, which the next section makes concrete.
Balanced, and unbalanced
Balanced is the odd one out, because it is a condition on height, not on where nodes sit. A tree is balanced when, for every node, its two subtrees differ in height by at most one.
every node has zero children or two, so this is full — and node 1's subtrees differ in height by 2, so it is not balanced
That figure is worth a second look, because it kills the most common wrong intuition about this vocabulary: full does not mean balanced. Every single node there has zero children or two, and the tree is still visibly lopsided. Shape rules and height rules are measuring different things.
Unbalanced is not a kind of tree you build. It is what you get when the balanced condition fails — and, as the next two articles show, it is what happens to a search tree by accident when data arrives in order.
Degenerate
A degenerate binary tree has exactly one child per internal node. Every level holds one node.
four nodes, height 3 — this is a linked list wearing a tree's type
This is the worst case, and it is not hypothetical. It has height n − 1 instead of log₂ n, so every operation that was supposed to be logarithmic is linear, and the left/right fields are pure overhead over a plain linked list.
How the shapes overlap
The five terms are not a ladder, and drawing them as one is where most explanations go wrong. The actual relationships:
- Perfect implies complete, full and balanced. All three, always. It is the strictest shape.
- Complete implies balanced, but says nothing about full — the complete figure above has a node with one child.
- Full says nothing about complete, and nothing about balanced. The full figure above has a gap in the middle; the unbalanced figure above is full and lopsided.
- Full and complete are independent in both directions. There are trees that are full and not complete, and trees that are complete and not full. Neither implies the other.
- Degenerate implies unbalanced, as soon as the tree is tall enough to have a lopsided subtree.
Height against node count
Everything above is scaffolding for one number. The height of a binary tree is what every operation costs, because the longest root-to-leaf path is the most work a search can be forced to do.
For a given node count n, the height depends entirely on shape, and the spread between the best and worst cases is enormous:
| Shape | Height for n nodes | At n = 1,000,000 |
|---|---|---|
| Perfect | log₂(n+1) − 1 | 19 |
| Complete | ⌊log₂ n⌋ | 19 |
| Degenerate | n − 1 | 999,999 |
That is the same million nodes, and a walk of 19 steps against a walk of a million. Not a constant factor — a difference in the shape of the growth.
The reason the good case is logarithmic is worth stating directly, because it comes up in every remaining article. Each level of a binary tree holds at most twice the level above it: 1, 2, 4, 8, 16. So a tree of height h holds at most 2^(h+1) − 1 nodes, and reading that backwards, n nodes need a height of at least log₂ n. Doubling your data adds one level.
Representing a Binary Tree in memory
Two children, two representations.
Linked nodes
The direct one: a struct with a value and two pointers. This is the linked-list node from earlier in the series with a second pointer bolted on, and everything about it should feel familiar.
The trick worth stealing there is the nil receiver. In Go a method can be called on a nil pointer, so defining Height() to return -1 for the empty tree means no caller ever checks for nil — the base case lives in one place instead of at every call site. It is the closest thing tree code has to a free lunch.
The array representation
The other representation drops the pointers entirely. Number the nodes level by level, left to right, starting at 0, and store them in a flat slice at those indices. The relationships become arithmetic:
That is the whole scheme. No Left field, no Right field, no allocation per node — one contiguous block, and a child's address computed from its parent's with a shift and an add.
node 1's children are at 2·1+1 = 3 and 2·1+2 = 4 · node 5's parent is at (5−1)/2 = 2
The payoff is real: no pointer chasing, no per-node allocation, and siblings sit next to each other in memory, so walking a level is a sequential read the CPU cache is built for. This is the opposite of the cache-hostile pointer chasing the linked-list article warned about.
The catch is that the indices are assigned by position, not by insertion order — so a missing node still consumes its slot. That makes the cost of this representation depend entirely on shape:
- On a complete tree it is free. The filled slots are exactly
0 .. n−1, contiguous, with nothing wasted. This is not a coincidence, and it is why "complete" earned its own name. - On a degenerate tree it is catastrophic. Height
n − 1means the deepest node's index is around2^n, so 21 nodes in a right-leaning chain need over two million slots.
Try it yourself
The five shapes are easier to feel than to memorise. Build a tree by clicking, and watch the classifications re-decide — then click any shape it fails to see exactly which node ruled it out.
click a ✗ to see what rules it out
Two things worth trying: load full and then check whether it is complete, and load complete and check whether it is full. Neither implies the other, and doing it by hand is more convincing than the paragraph above.
Common operations and their costs
The same operations, on the same node count, in the best and worst shapes — which is the whole point of the article in one table:
| Operation | Complete tree | Degenerate tree |
|---|---|---|
| Reach the deepest node | ||
| Find a value | ||
| Count nodes, measure height | ||
| Array slots needed |
Read the first row and the last one together. Shape does not change what a binary tree can do — it changes what it costs, by an unbounded factor.
And notice what is still O(n) in both columns: finding a value. Nothing in this article tells you which way to go at a node, so a search still has to consider everything. That gap is exactly what the next article closes.
Binary Trees in the real world
Expression and parse trees
Every binary operator is a node with two children — its operands. 2 * (3 + 4) is a * node whose children are 2 and a + node. Compilers and calculators build these, and evaluating one is a matter of resolving children before parents. The two-child shape is not a design choice here; it falls out of the operators being binary.
Huffman coding
The compression behind ZIP and JPEG builds a binary tree where every left branch is a 0 bit and every right branch a 1. A character's code is its path from the root, so frequent characters are placed shallow and get short codes. The tree is the codebook.
Heaps and priority queues
The array representation above, used at full strength. Schedulers, event loops and timers are almost always backed by one. This gets its own article at the end of the series.
Binary space partitioning
Games and renderers split space in half repeatedly — each node is a region, its two children the halves. Doom famously used a BSP tree to decide draw order. Same idea in collision detection and ray tracing.
Merkle trees
Git commits, blockchain blocks and rsync all hash pairs of nodes upward, so a single root hash certifies an entire dataset and a mismatch can be localised in log n comparisons. Here the tree encodes verification rather than order — a use for the shape that has nothing to do with searching.
When Binary Trees fall short
Two children is often the wrong number. A filesystem directory holds many entries, a DOM element wraps many children. Forcing those into a binary tree means either the first-child/next-sibling trick from the previous article or a lot of pretending. Use the shape that matches your data, not the one with the nicest math.
Nothing keeps the tree short. Every good property in this article assumed a tidy shape, and the definition guarantees none of it. This is the single biggest caveat, and the next two articles are about it: first watching a search tree degenerate from ordinary input, then fixing it.
The array representation only pays off when complete. It is the fastest layout available and a trap everywhere else. Reaching for it on a tree whose shape you do not control turns a memory optimisation into exponential waste.
Still no ordering. A binary tree constrains where nodes can be, not which values go where. Search is O(n) in the best shape and the worst. The structure is now predictable, but it is not yet useful for lookup.
Pointer chasing, unless you flattened it. In the linked representation each node is its own allocation, so a walk is a sequence of potential cache misses — the same cost the linked-list article described, and the reason the array representation exists at all.
Summary
Binary trees take the general tree and cap the children at two, which turns a container into something predictable:
- At most two children, and they are named —
leftandrightare not interchangeable, and that asymmetry is what later articles build on - Full, complete, perfect, balanced, degenerate — full and complete constrain different things and imply nothing about each other; perfect implies all three
- Balanced is a height rule, not a shape rule — a full tree can be badly unbalanced, which is the intuition most people get wrong
- Height is the cost —
log₂ nin a tidy tree againstn − 1in a degenerate one, which is 19 steps against a million at the same node count - A complete tree fits an array exactly —
2i+1,2i+2,(i−1)/2, no pointers and no waste, and exponential waste on any other shape - Search is still O(n) — the shape is constrained, the values are not
The key insight is that the two-child limit buys predictability, not speed. Capping the children is what makes height a function of node count and makes a child's address computable from its parent's — but neither of those tells you where a value lives. A binary tree is a shape you can reason about, holding data you still have to search exhaustively.
The next article adds the one rule that fixes it. Decide that everything in a node's left subtree is smaller than the node and everything in its right subtree is larger, and suddenly every comparison at a node discards half the remaining tree — the twenty-questions game from the top of this article, made into a data structure.