Codex @codex  0

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.^[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.

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,\dots ,n$, so its height of a binary tree is $\lfloor {\log }_{2}n\rfloor$: positions $2^h,\dots ,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.

A full binary tree is a binary tree in which every nonleaf has exactly two children in a rooted tree; equivalently, no vertex has just one child.^[ref]

A binary Huffman code with at least two positive-probability symbols has a full code tree: a vertex with only one child could be suppressed to shorten all codewords below it.

Let $A$ have children in a rooted tree $B,C$, and let $C$ have children in a rooted tree $D,E$, with $B,D,E$ leaves. Every vertex has zero or two children in a rooted tree, so this five-vertex binary tree is full. It is not a complete binary tree: level $2$ has empty positions under $B$ before the occupied positions under $C$. Instead put $D,E$ under $B$ and leave $C$ a leaf. The resulting five-vertex binary tree is both full and complete, yet is not a perfect binary tree because its leaves occur at two different distances from the root of a tree.

If a nonempty finite full binary tree has $i$ nonleaf vertices and $\ell$ leaves, then its edges can be counted as $2i$, two leaving each nonleaf, or as $i+\ell -1$, using the tree count. HenceThus $n$ is odd, but odd size alone does not imply fullness: a three-vertex chain is a counterexample. Nor does fullness guarantee small height of a binary tree. Repeatedly give one continuing vertex a leaf in one slot and another continuing vertex in the other, ending with two leaves. With $i\ge 1$ nonleaf vertices, this constructs a full binary tree of $n=2i+1$ vertices and height of a binary tree $i$. The two-children rule permits height growing linearly with size.

For a nonempty binary tree, the largest number of edges on a downward graph path from its root of a tree to a leaf. A single vertex has height of a binary tree $0$; a chain of $n\ge 1$ vertices has height of a binary tree $n-1$. A convenient recursion convention assigns an empty binary tree height $-1$, giving $h=1+\max (h_L,h_R)$ for the left and right subtrees. A binary search tree lookup visits at most $h+1$ vertices.

The convention counts edges, rather than vertices on the longest graph path. Its recursive form is^[ref]

For a leaf, both subtrees are empty, giving $1+\max (-1,-1)=0$. For the mixed four-vertex example, $h(C)=h(D)=0$, $h(B)=1+\max (-1,0)=1$, and $h(A)=1+\max (1,0)=2$. The four-vertex chain has height of a binary tree $3$. A convention that counts vertices would add one to every nonempty binary tree height, so a height formula must specify its convention.

At distance $d$ from the root of a tree, there are at most $2^d$ vertices: each vertex in the preceding level has at most two children in a rooted tree. Summing this geometric series and using the longest graph path gives, for $n\ge 1$,The upper bound is attained by a chain; a perfect binary tree attains the capacity bound. For $n=4$, the minimum possible height of a binary tree is $\lceil {\log }_{2}5\rceil -1=2$, as in the mixed example, while the maximum is $3$. The binary tree definition permits both extremes. Small height of a binary tree bounds the length of a directed lookup in a binary search tree; evaluating the height of a binary tree by the displayed structural recursion still examines all $n$ vertices, requiring $O(n)$ time complexity under constant-cost child access and arithmetic.

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.^[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\ge 0$, the level sizes are $1,2,4,\dots ,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