Counting Vertices in Full Binary Trees

Full Binary Trees and Their Counts

A full binary tree has a particularly rigid branching rule: each vertex either has no children or has exactly two. This restriction links the number of branching vertices to the number of leaves. The resulting formulas are useful for checking a proposed tree, estimating how many vertices a recursive structure contains, and distinguishing a full binary tree from a tree in which vertices are merely allowed to have at most two children.

All trees in this tutorial are finite, simple, undirected trees with a specified root. A tree is connected and has no cycles. In a rooted tree, every vertex other than the root has a unique parent: the neighboring vertex immediately preceding it on the unique path from the root. The children of a vertex are its neighbors for which it is the parent.

Definition: A vertex of a rooted tree is a leaf if it has no children. It is an internal vertex if it has at least one child. A rooted tree is full binary if every internal vertex has exactly two children. Thus, each vertex of a full binary tree has either zero or two children. The tree consisting of one root and no edges is full binary: its root is a leaf and there are no internal vertices.

Write $i$ for the number of internal vertices, $\ell$ for the number of leaves, and $n=|V|$ for the total number of vertices. Since every vertex is one or the other, $n=i+\ell$. The key count is obtained by counting the edges in two different ways.

Counting Edges by Their Parent Endpoints

Proposition: If a finite rooted full binary tree has $i$ internal vertices and $m$ edges, then $m=2i$.

Proof. Each internal vertex has exactly two children, so it is the parent of exactly two vertices. Each leaf has no children, so it is the parent of zero vertices. Every edge joins a parent to one of its children, and every vertex other than the root has exactly one parent. Therefore counting edges by their parent endpoint counts each edge exactly once. The internal vertices contribute two edges each and the leaves contribute none, giving $m=2i+0\ell=2i$. This also covers the one-vertex tree: there are no internal vertices and no edges, so $m=0=2\cdot0$. $\square$

There is another count of the same edges. A finite tree with $n$ vertices has $n-1$ edges. Applying this standard tree edge count together with the proposition gives $n-1=2i$. The next theorem states both resulting vertex formulas.

Theorem: If a finite rooted full binary tree has $i$ internal vertices, $\ell$ leaves, and $n$ vertices in total, then $$ \ell=i+1 \qquad\text{and}\qquad n=2i+1. $$

Proof. The tree is connected and acyclic, so the tree edge count gives $m=n-1$. By the proposition, the same number of edges is $m=2i$. Equating these counts gives $n-1=2i$, hence $n=2i+1$. Also $n=i+\ell$, because every vertex is either an internal vertex or a leaf, and these two sets are disjoint. Substituting $n=2i+1$ into $n=i+\ell$ gives $i+\ell=2i+1$, so $\ell=i+1$. The argument includes $i=0$: the one-vertex tree has $n=1$ and $\ell=1$, as the formulas state. $\square$

The identities have a direct interpretation. Each internal vertex creates two parent-child edges, so there are $2i$ edges. But a tree with $n$ vertices has only $n-1$ edges. This forces $n=2i+1$; after the $i$ internal vertices are accounted for, the remaining $i+1$ vertices are leaves.

Worked Examples

Worked Example: The One-Vertex Tree

Let the rooted tree have vertex set $V=\{r\}$, edge set $E=\varnothing$, and root $r$. Since $r$ has no children, it is a leaf. There are no internal vertices, so $i=0$; there is one leaf, so $\ell=1$; and the total number of vertices is $n=1$.

Substituting $i=0$ into the formulas gives $2i+1=2\cdot0+1=1$ total vertex and $i+1=0+1=1$ leaf. Both agree with the explicit counts. Independently, the edge count is $m=0$, while $2i=2\cdot0=0$, so the edge-count proposition also holds.

Check: $n=1$, $2i+1=2\cdot0+1=1$, $\ell=1$, and $i+1=0+1=1$.

Worked Example: A Full Binary Tree with Three Internal Vertices

Let $V=\{r,a,b,c,d,e,f\}$, $E=\{ra,rb,ac,ad,be,bf\}$, and root $r$. The root $r$ has children $a,b$; vertex $a$ has children $c,d$; and vertex $b$ has children $e,f$. Vertices $r,a,b$ each have two children, while $c,d,e,f$ have none. Thus the tree is full binary, with internal vertices $\{r,a,b\}$ and leaves $\{c,d,e,f\}$.

Counting directly gives $i=3$, $\ell=4$, and $n=7$. The vertex formulas give $2i+1=2\cdot3+1=7$ and $i+1=3+1=4$. The edge list contains six edges. Counting from the internal vertices gives two edges from $r$, two from $a$, and two from $b$, for $2+2+2=6$; the tree edge count gives $n-1=7-1=6$.

Check: The two edge counts agree, $6=2\cdot3$, and the direct counts agree with the formulas: $7=2\cdot3+1$ and $4=3+1$.

Worked Example: A Full Binary Tree with Unequal Branching Depths

Let $V=\{r,a,b,c,d,e,f,g,h\}$, $E=\{ra,rb,ac,ad,ce,cf,bg,bh\}$, and root $r$. The parent-child pairs are $r$ with $a,b$, $a$ with $c,d$, $c$ with $e,f$, and $b$ with $g,h$. Each of $r,a,c,b$ has two children; each of $d,e,f,g,h$ has none. The tree is full binary even though the leaves are not all at the same distance from the root.

There are $i=4$ internal vertices, namely $r,a,c,b$, and $\ell=5$ leaves, namely $d,e,f,g,h$. The vertex set has $n=9$ elements. The formulas give $2i+1=2\cdot4+1=9$ and $i+1=4+1=5$. The edge list has eight edges: each of the four internal vertices contributes two, giving $2+2+2+2=8$. The tree edge count independently gives $n-1=9-1=8$.

Check: The direct counts satisfy $n=i+\ell=4+5=9$; the formula gives $n=2\cdot4+1=9$; and the leaf count gives $\ell=4+1=5$.

Why the Fullness Condition Matters

The formulas depend on every internal vertex having exactly two children. If a vertex may have just one child, then counting edges from internal vertices no longer gives $2i$: a vertex with one child contributes one edge instead of two. The tree edge count $m=n-1$ still holds, but the equation $m=2i$ does not follow.

For instance, take $V=\{r,a\}$, $E=\{ra\}$, rooted at $r$. This is a binary tree under the convention “at most two children,” but it is not full binary: $r$ has one child. It has $i=1$, $\ell=1$, and $n=2$. Applying the full-tree formula would predict $n=2\cdot1+1=3$ and $\ell=1+1=2$, neither of which matches this tree. The error is not in the formulas; the hypothesis of fullness is absent.

Takeaway: In a finite rooted full binary tree, counting child edges gives $m=2i$, while the tree property gives $m=n-1$. Together with $n=i+\ell$, these yield $n=2i+1$ and $\ell=i+1$. Always check that each internal vertex has exactly two children before using these identities.

Common Miscount

A frequent mistake is to remember $n=2i+1$ but conclude that the number of leaves is $i$, rather than $i+1$. The internal vertices are only part of the total: the leaf count must be found by subtracting the internal vertices from the total. For the explicit tree with $i=3$, the incorrect calculation would say “three internal vertices, therefore three leaves.” The correct subtraction is $n-i=(2i+1)-i=i+1$, which for $i=3$ gives $7-3=4$ leaves. The example's leaf set $\{c,d,e,f\}$ confirms the corrected count.

A second useful check is to count edges both ways. If a proposed full binary tree has $i=3$, its internal vertices must contribute $2\cdot3=6$ edges. If the stated vertex count is $7$, a tree on those vertices has $7-1=6$ edges. A mismatch between these counts signals either a mistaken count or a tree that is not full binary.

Check Your Understanding

Use the definitions and counting arguments above. When testing a formula, state whether the tree is full binary.

A full binary tree has $i=5$ internal vertices. Find its number of leaves and its total number of vertices.
Can a full binary tree have $i=0$ and $\ell=0$? Justify your answer, including the role of the root.
Let $V=\{r,a,b,c\}$, $E=\{ra,rb,ac\}$, rooted at $r$. Is this tree full binary? Which vertex counts can you determine directly, and may the full binary formulas be applied?
Explain why counting edges by their parent endpoints counts every edge exactly once in a rooted tree.
A claimed full binary tree has $i=4$, $n=10$, and $\ell=6$. Which of these counts is inconsistent with the theorem?