Suppose you are given a binary tree with n nodes, such that each node has…
2016
Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be
- A.
\(\frac n 2 - 1\) - B.
\(\frac n 2 + 1\) - C.
\((n - 1) / 2\) - D.
\((n + 1) / 2\)
Attempted by 164 students.
Show answer & explanation
Correct answer: C
Key idea: relate the number of internal nodes and leaves in a full (0-or-2-child) binary tree.
Let i be the number of internal nodes (nodes with two children) and l be the number of leaves (nodes with zero children).
In a full binary tree every internal node contributes exactly two children, so the number of leaves satisfies l = i + 1.
Total nodes n = i + l = i + (i + 1) = 2i + 1, so i = (n - 1) / 2.
To maximize height, arrange the internal nodes along a single root-to-internal-node chain where each internal node has one child that continues the chain and the other child as a leaf. This uses all internal nodes while producing the longest root-to-leaf path.
The maximum height (measured as number of edges on the longest root-to-leaf path) equals the number of internal nodes on that path, which is i = (n - 1) / 2.
Therefore the maximum height is (n - 1) / 2.