 Full binary tree

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.