How do full, complete, perfect and height-balanced binary trees differ from one another?

## Four properties, three different concerns These words get used as if they were degrees on one scale from "messy" to "tidy". They are not. Each one constrains a different aspect of the shape, which is why the implications between them run only one way. | term | what it constrains | what it buys you | |---|---|---| | full | every node has 0 or 2 children | leaves = internal nodes + 1; clean induction proofs | | complete | levels filled top to bottom, last level packed left | height is exactly floor(log2 n); gap-free flat storage | | perfect | full and complete with all leaves on one level | exactly 2^(h+1) - 1 nodes, 2^h leaves | | height-balanced | sibling subtree heights differ by at most a constant | height stays Θ(log n) under arbitrary insert order | ### Full (sometimes called strictly binary) Every node has either two children or none — no node with a lone child. This says nothing about levels. A "caterpillar" shape where the root has one leaf child and one internal child, repeated all the way down, is perfectly full and has height about n/2. So **full does not mean short**, and full trees can be as degenerate as any chain. The property that makes full trees pleasant is the counting identity: in a full binary tree, the number of leaves is always one more than the number of internal nodes. Anything that pairs items until one remains — a merge schedule, a knockout structure — inherits that identity. ### Complete Every level is completely filled except possibly the deepest, and that deepest level is filled contiguously from the left. This is a statement purely about *where the holes are allowed to be*: only at the right end of the bottom row. Two consequences follow. First, a complete tree with n nodes has height exactly floor(log2 n), the smallest height any n-node binary tree can have. Second, the nodes can be laid out in a flat block of n slots, level by level, with no wasted space, and the structure recovered by arithmetic instead of stored links: numbering from 0, the children of slot i are 2i+1 and 2i+2 and the parent of i is floor((i-1)/2); numbering from 1 instead, the children are 2i and 2i+1 and the parent is floor(i/2). That off-by-one between the two numbering schemes is the single most common whiteboard slip on this material — pick a base, write the first two rows out by hand, and check the formulas against them before you use them. Note what completeness is *not*: a complete tree may have a node with exactly one child (the leftmost node of the bottom row can be a lone left child), so complete does not imply full. ### Perfect All internal nodes have two children and all leaves sit on the same level. A perfect tree of height h has 2^h leaves, 2^h - 1 internal nodes and 2^(h+1) - 1 nodes in total. Perfect trees exist only for those exact node counts, which is why they show up in proofs, in counting arguments and in structures deliberately padded to a power of two, but almost never as the shape real data takes. ### Height-balanced A balance condition is a *local* rule enforced at every node — most commonly that the heights of its two subtrees differ by at most one — whose *global* consequence is that the height of the whole tree stays proportional to log2 n. It is the only one of the four properties defined by an inequality rather than by a fill pattern, and the only one you can maintain incrementally under arbitrary insertion order. This is where the misconception lives. "Balanced" does not mean the two sides have equal height, and it does not mean the tree looks symmetric. Take a root whose left subtree has height 2 and whose right subtree has height 1: the difference is 1, the condition holds, and the drawing is visibly lopsided. Repeat that skew at every level and you get a legal balanced tree that is noticeably taller than the complete tree with the same node count — still Θ(log n), just with a larger constant. That is the deal balancing offers: give up the perfect picture, keep the asymptotic guarantee, and get it cheaply on every insert. ## Which property do you actually need? In practice, completeness is a *representation* requirement — it is what makes gap-free flat storage possible. Balance is a *performance* requirement — it is what bounds the cost of every root-to-leaf operation. Full and perfect are mostly *analysis* vocabulary: they make counting arguments and base cases clean. When an interviewer asks which one your structure needs, answering "balanced, because operations cost O(h) and I need h in O(log n)" shows you know why the vocabulary exists rather than merely what the words mean.