Computer Science, asked by jyoti78, 1 year ago

prove by induction that

(i) The number of leaves in a binary tree

of height 'h' are less than or equal to

2h.

(ii) The number of nodes in a full binary

tree of height 'h' are equal to

(2h+1 _ 1).

Answers

Answered by kvnmurty
10
1)  Binary tree the number n of leaves at height h  <= 2h.
   
 In a binary tree of height h = 1, there is only one node.  
    Number of nodes n = 1.   Hence  n <= 2h is true.

  Let us say at height H the number N of nodes is <= 2H.
  Then at height H+1 the number M of nodes will be  <= 2 * N.
  Because each of N nodes can have at most two children nodes. 
      So at height H+1 ,  number of nodes <= 2 * N  <= 2 * (2 H)
                 or  <= 2 (H +1) + 2 (H-1)

Since   H-1 >=0,    the number of nodes at height H+1  <= 2 (H+1).

   Hence the given hypothesis is proved by Mathematical Induction.

================
2. Total Number N of nodes in a full binary tree of height n are:  N = 2ⁿ - 1.

For a binary tree of height n = 1, there is one node, ie, N = 1.
        So   N = 2¹ - 1 = 1.  So it is true.

In a full binary tree the number N of nodes at a height n will be = 2ⁿ⁻¹.  This is clearly known as N follows the geometric series :  1, 2 , 4, 8 , 16 ....

Let us say for a height n the total number of nodes is = N = 2ⁿ - 1.

The number of nodes in the next level (height n+1) will be = 2⁽ⁿ⁺¹⁾ ⁻ ¹ = 2ⁿ.

Total number of nodes in a tree of height n+1 will be then:
           =  N + 2ⁿ =  2ⁿ -1 + 2ⁿ = 2ⁿ⁺¹ - 1.

Hence the given hypothesis is proved by Math Induction.

kvnmurty: :-)
Similar questions