PadhaikoAll subjects

Past exam question: 2073 Bhadra (Regular), Q7

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

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).

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.

All past exam questions for Data Structure and Algorithms