GATE CSE 1993 | Question: 16

Question

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.

Answer 1

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.

Comments

A descendant of a node N is either N itself, a child of N, a child of a child of N and so on for any number of levels .. We say node N is an ancestor of node M if M is a descendant of N ...

---

@Puja Mishra..."A descendant of a node N is either N itself, ......"

Can we call a node a descendant of itself?

---

Consider a node x in a rooted tree T with root r. We call any node y on the
unique simple path from r to x an ancestor of x. If y is an ancestor of x, then x is
a descendant of y. (Every node is both an ancestor and a descendant of itself.) If y
is an ancestor of x and x ¤ y, then y is a proper ancestor of x and x is a proper
descendant of y. The subtree rooted at x is the tree induced by descendants of x,
rooted at x.                                               - Cormen Introduction to Algorithms

Yes , every node is both ancestor and descendent of itself

Answer 2

**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

Comments

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

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

---

Sir ,how this come "total node= 2*non_leaf node  + 1  "

Answer 3

Here we need to first understand on what should we apply induction . First of all it can't be on the number of nodes in the tree as each non-leaf node has $2$ nodes. So the induction must be on the level of the binary tree. Let $x_{k}$ denote the number of non-leaf nodes and $y_{k}$ the number of leaf nodes when the binary tree is in $k$-th level. We neee to establish that for $k≥0$,

$$x_{k}=y_{k}-1   ..........eq(1)$$

BASE CASE:-

 At level-0 there is only one node (which is also the leaf node). Here $x_{0}=0$ and $y_{0}=1$ which is in accordance with eq$1$. This establishes the base case.

INDUCTION STEP

Let eq$1$ be true until level-$k$. We will prove it to be true for $k+1$. Hence,

$$x_{k}=y_{k}-1$$

Let's get to the level-$k+1$. Now,

$$y_{k+1}=2y_{k}$$ and 

$$x_{k+1}=x_{k}+y_{k}$$

It's easy to verify that,

$$x_{k+1}=y_{k+1}-1$$ from the above two equations.

CONCLUSION:-

 By the induction step it could be concluded that for all $k≥0 $,

$$x_{k}=y_{k}-1  $$

Comments

I think you meant k to be height of the tree rather than level

---

No, here $k$ is level of the tree and not it's height.