Past exam question: 2073 Bhadra (Regular), Q7
Open in the Padhaiko appQuestion
Prove that strictly binary tree with a n leaves contain 2n-1 nodes.
Solution
Proof by Mathematical Induction on Number of Leaves : A strictly (full) binary tree is a binary tree in which every node has either children (a leaf) or children (an internal node).
- Base Case (): A tree with leaf consists of a single root node (which is a leaf). Total nodes = . The claim holds for .
- Inductive Hypothesis: Assume every strictly binary tree with leaves () contains total nodes.
- Inductive Step (for leaves): Any strictly binary tree with leaves has a root with two non-empty strictly binary subtrees and . Let have leaves and have leaves, where and . By the inductive hypothesis:
- Nodes in
- Nodes in Total nodes in :
Alternative Degree-Counting Proof: Let be the number of leaves and be the number of internal nodes (each of out-degree ). Total edges = , and every node except the root has 1 incoming edge, so total nodes . Also , giving , hence .
Answer:
By induction (and edge-counting ), a strictly binary tree with leaves has internal nodes and total nodes.