15 votes

Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has $2$-descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

15 votes

Best answer

**Base Case :- **When we have just root then, there are no non leaf nodes. So No of leaves $= 1$, No of non leaf nodes is $= 0$. Base case holds.

**Induction Hypothesis** :- Assume that now for $k$ internal nodes we will have $k+1$ leaves.

**Inducting **on no of leaves, Now we add $2$ more leaves to this tree. One of $k+1$ leaf will become internal node. So now we will have $k+1$ internal node. No of leafs will be $K+ 1 - 1$ ($1$ leaf just became internal node) $+ 2$(New leafs) . So we proved that for any binary tree, in which every non-leaf node has $2$-descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

0

@set2018

Descendant: A node reachable by repeated proceeding from parent to child. So for every non-leaf node, we must be having two nodes which can be obtained by proceeding from parent to child.

Ref: https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology_used_in_trees

7 votes

**descendents mean immediate child or no of node from that node to leaf ??

if immediate then :

let total n nodes are in binary tree.

2*non_leaf node + 1 = total node

non leaf node = (total node -1)/2 = (n-1)/2

no of leaf node + no of nonleaf node = total node

no of leaf node + (n-1)/2 = n

no of leaf node = (n+1)/2

= (n-1 + 2)/2

= (n - 1)/2 + 1

= no of non leaf node + 1

if immediate then :

let total n nodes are in binary tree.

2*non_leaf node + 1 = total node

non leaf node = (total node -1)/2 = (n-1)/2

no of leaf node + no of nonleaf node = total node

no of leaf node + (n-1)/2 = n

no of leaf node = (n+1)/2

= (n-1 + 2)/2

= (n - 1)/2 + 1

= no of non leaf node + 1

0

Descendant: A node reachable by repeated proceeding from parent to child..

Ref: https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology_used_in_trees