Question

The height of a binary tree is the number of edges in the longest path from the root
to a leaf in the tree. The maximum possible height of a full binary tree with
23 nodes is _________. (answer in integer)

Hint:

For a full binary tree, node count N relates to internal nodes I by N = 2I + 1; the maximum height is achieved by a skewed caterpillar-shaped tree with one internal node per level.

Answer 1

Correct Answer: 11

Step 1: In a full binary tree, every node has either 0 children (a leaf) or exactly 2 children. This forces the number of leaves to be exactly one more than the number of internal (2-child) nodes: if \(N\) is the total nodes, \(I\) the internal nodes and \(L\) the leaves, then \(N = I + L\) and \(L = I + 1\), giving \(N = 2I + 1\).

Step 2: With \(N = 23\), we get \(23 = 2I+1\), so \(I = 11\) internal nodes and \(L = 12\) leaves.

Step 3: To maximize the height (the number of edges on the longest root-to-leaf path), the tree must be as skewed as possible while still remaining a full binary tree. This is achieved by a caterpillar-shaped tree: every internal node except the last has one leaf child and one internal child that continues the chain; the last internal node has two leaf children.

Step 4: In this skewed shape, the 11 internal nodes occupy levels 0 through 10 (one per level), and the two deepest leaves, children of the last internal node, sit at level 11. So the longest root-to-leaf path has 11 edges.

Step 5: This arrangement uses exactly 11 internal nodes and 12 leaves (one side leaf at each of levels 1 to 10, plus 2 leaves at level 11), matching \(N = 23\) and giving the tallest possible full binary tree with this many nodes.

Final Answer: \[\boxed{\text{Maximum height} = 11}\]