A 3-ary tree is a tree where every internal node has exactly 3 children. Use induction to prove that the number of leaves in a 3-ary tree with n internal nodes is 2(n – 1) + 3.
The Correct Answer and Explanation is:
To prove by induction that the number of leaves LL in a 3-ary tree with nn internal nodes is: L=2(n−1)+3=2n+1L = 2(n – 1) + 3 = 2n + 1
✅ Base Case:
Let n=1n = 1 (a tree with one internal node).
- Since it’s a 3-ary tree, the one internal node has exactly 3 children.
- These 3 children must be leaves, because there are no other internal nodes.
So:
- Number of leaves L=3L = 3
- Check the formula:
2n+1=2(1)+1=32n + 1 = 2(1) + 1 = 3 ✔
✅ Base case holds.
✅ Inductive Hypothesis:
Assume the formula holds for some n=kn = k, i.e.,
A 3-ary tree with kk internal nodes has: L=2k+1 leavesL = 2k + 1 \text{ leaves}
✅ Inductive Step:
We must prove that a tree with k+1k+1 internal nodes has: L=2(k+1)+1=2k+3 leavesL = 2(k+1) + 1 = 2k + 3 \text{ leaves}
Start with the 3-ary tree of kk internal nodes and 2k+12k + 1 leaves.
Now, add 1 internal node by replacing one leaf with a new internal node having 3 children.
- That removes 1 leaf (the one we replaced)
- Adds 3 new leaves (the children of the new internal node)
- So, net change in leaves: +2+2
(remove 1, add 3 → L′=(2k+1−1+3)=2k+3L’ = (2k + 1 – 1 + 3) = 2k + 3)
Thus, a 3-ary tree with k+1k+1 internal nodes has 2k+3=2(k+1)+12k + 3 = 2(k+1) + 1 leaves.
✅ Inductive step proven.
✅ Conclusion:
By mathematical induction, in any 3-ary tree with nn internal nodes, the number of leaves is: L=2n+1=2(n−1)+3L = 2n + 1 = 2(n – 1) + 3
Q.E.D.
