= Complete binary tree
A <complete binary tree> is a <binary tree> whose levels are full except possibly the deepest, which is filled from left to right with no gaps.<Data Structures and Algorithms edited by Peter Ljunglöf and others/9.1 Binary trees>[Data Structures and Algorithms, section 9.1.1: complete shape and binary heap example]{ref}
Here a level groups <vertices> by their <graph distance> from the <root of a tree>. A <binary heap> uses this shape to maintain logarithmic <height of a binary tree>. Completeness differs from the two-children condition of a <full binary tree>.
\Image[/binary-tree-full-complete-perfect.png]
{title=<Full binary trees>, <complete binary trees>, and <perfect binary trees> impose different shape conditions}
{description=Each panel states all three properties. Outlined positions expose gaps in the last level. In particular, the five-<vertex> example in the lower left is both full and complete but is not perfect.}
For a six-<vertex> example, give $A$ two <children in a rooted tree> $B,C$, give $B$ two <children in a rooted tree> $D,E$, and give $C$ only a left child $F$. The levels have $1,2,3$ <vertices>, and the last occupies its first three positions, so this is a <complete binary tree>. It is not a <full binary tree>, since $C$ has exactly one child. Moving $F$ to the right slot of $C$ preserves $n=6$ and <height of a binary tree> $2$, but leaves a gap before $F$ and destroys completeness. Merely keeping the deepest <vertices> near the left side is insufficient; every earlier position must be occupied.
Number positions by the left-to-right level order of <breadth-first search>, beginning with root position $1$. The children of position $i$ have positions $2i$ and $2i+1$. A nonempty <complete binary tree> occupies exactly positions $1,\ldots,n$, so its <height of a binary tree> is $\lfloor\log_2 n\rfloor$: positions $2^h,\ldots,2^{h+1}-1$ form level $h$. This consecutive occupancy explains the compact <array> representation of a <binary heap>, while <heap order> is a separate condition on values. Neither completeness nor the <binary tree> definition supplies the <binary search tree> ordering rule.
Back to article page
