= Perfect binary tree
{title2=$n=2^{h+1}-1$}
A nonempty <binary tree> in which every level, including the deepest, contains all its possible <vertices>. Equivalently, it is a <full binary tree> whose leaves are all at the same <graph distance> from the <root of a tree>.<Data Structures and Algorithms edited by Peter Ljunglöf and others/9.1 Binary trees>[Data Structures and Algorithms, section 9.1.1: perfect shape, equal leaf levels, and Figure 9.4]{ref}
Every <perfect binary tree> is both a <full binary tree> and a <complete binary tree>; the five-<vertex> example above shows that the converse fails even when both properties hold. These definitions fix the terminology used here.
For <height of a binary tree> $h\geq0$, the level sizes are $1,2,4,\ldots,2^h$, giving $n=2^{h+1}-1$ by a <geometric series>. There are $2^h$ leaves. The seven-<vertex> example has level sizes $1,2,4$ and <height of a binary tree> $2$; the single-<vertex> <binary tree> is already perfect, with $h=0$. More generally, joining two <perfect binary trees> of equal <height of a binary tree> under a fresh <root of a tree> gives the next such shape. Equal heights are essential: fullness alone allows unequal leaf distances. A <perfect binary tree> realizes the maximum number of <vertices> for its <height of a binary tree>, making the exponential capacity behind short lookup <graph paths> visible.
// Target: probability-and-statistics.bigb
Back to article page
