Full binary tree
= 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.<Data Structures and Algorithms edited by Peter Ljunglöf and others/9.1 Binary trees>[Data Structures and Algorithms, section 9.1.1: full shape and Huffman coding tree example]{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. Hence
$$
\ell=i+1,\qquad n=i+\ell=2i+1.
$$
Thus $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\geq1$ 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.