In a full binary tree of height \(k\), there are ______ internal nodes.

Concept

A perfect binary tree is one in which every level is completely filled: every internal node has exactly two children AND every leaf sits at the same depth. Measure height as the number of edges on the longest root-to-leaf path, so the root sits at level/depth \(0\). Such a tree of height \(k\) then spans levels \(0\) through \(k\); level \(i\) holds exactly \(2^i\) nodes; levels \(0\) through \(k-1\) are entirely internal, and level \(k\) is entirely leaves.

Two conventions have to be pinned down before the blank has a single value, and the offered choices pin down both. First, “full binary tree” is used here in the filled-level sense above, i.e. as a synonym for perfect — the convention this exam and many data-structure texts follow. Under the stricter sense that some texts reserve for “full” (every node has either zero or two children), height alone does not fix the internal-node count at all: a height-\(k\) tree of that kind can have anywhere from \(k\) internal nodes (a caterpillar, where each internal node has one leaf child and one internal child) up to \(2^k - 1\) (the filled tree), so no single expression could fill the blank. The choices on offer therefore only make sense under the filled-level reading.

Second, height is counted in EDGES here, not in levels. If height instead meant the number of levels (root at height \(1\)), a filled tree of height \(k\) would hold \(2^k - 1\) nodes in total and \(2^{k-1} - 1\) internal nodes — an expression that appears nowhere among the choices. The edge-counted convention is the one this item intends.

Application

1. The internal levels of a height-\(k\) full binary tree are level \(0\), level \(1\), \(\ldots\), level \(k-1\).

2. Level \(i\) has \(2^i\) nodes, so the internal-node count is the sum \(2^0 + 2^1 + \cdots + 2^{k-1}\).

3. This is a geometric series with ratio \(2\); its sum is \(2^k - 1\).

4. So a full binary tree of height \(k\) has \(2^k - 1\) internal nodes.

Cross-check

Summing all levels \(0\) through \(k\) gives the total node count \(2^{k+1} - 1\), and level \(k\) alone gives \(2^k\) leaf nodes. Subtracting, internal nodes \(= (2^{k+1}-1) - 2^k = 2^k - 1\), which matches the direct sum above.

A second, independent check uses the identity that holds whenever every internal node has exactly two children: the leaf count equals the internal-node count plus one, \(L = I + 1\). Here \(L = 2^k\), so \(I = 2^k - 1\) again. Concretely, at \(k = 2\) the tree has a root, \(2\) children and \(4\) leaves — \(7\) nodes in all, of which \(3\) are internal, and \(2^2 - 1 = 3\).