edited by
22,451 views
64 votes
64 votes

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h > 0$, then the minimum number of nodes in the tree is

  1. $2^{h-1}$
  2. $2^{h-1} + 1$
  3. $2^h - 1$
  4. $2^h$
edited by

7 Answers

Best answer
57 votes
57 votes
Correct Option: B

Since the difference between the nodes in left and right subtree must hold for every node, until the  last to last to last level, all levels must be fully filled. So, we get $2^{h−1}−1$ nodes (No. of nodes in a complete binary tree of height $h−2$). Now, our aim is to increase two more levels by adding minimum no. of nodes- just add two in nodes one below other to any of the nodes. So, we get $2^{h−1}+1$ nodes.
selected by
46 votes
46 votes

Option Elimination

Take a tree which satisfies given constraint   

and eliminate the incorrect options

h=1 n=2

Option A & C eliminated

Option B,D still satisfying

In below img h=2 n=3

Here option D eliminated

So option B is Ans

edited by
28 votes
28 votes

For a given node $a$, let the number of nodes in its left sub-tree be $l$ and that on the right sub-tree be $r$. Based on the given constraint $\mid l - r \mid \leq 2.$ For simplicity we can assume $l \geq r$ as this should be similar to assuming $ r \geq l$ and won't change the answer. This gives $r \geq l - 2.$

Now, minimum number of nodes in the sub-tree rooted at $a = l + r + 1$

$\qquad = l + l - 2 + 1$

$\qquad = 2l - 1\qquad \to (1).$

Now, lets assume the height of the sub-tree rooted at $a$ to be $h$ and this gives the height of its left (or right) sub-tree $ = h - 1.$

If we denote the minimum number of nodes in a binary tree of height $h$ satisfying the given conditions by $N(h),$ we get

$N(h) = 2 N(h-1) - 1$

We know $N(1) = 2.$

 So, from $N(h) = 2N(h-1)-1$ we get

$N(2) = 2 . 2 -1 = 3, N(3) = 5, N(4) = 9, N(5) = 17.$

We can see that $N(h) = 2^{h-1} +1.$

(Formal proof given below)


$N(h) = 2N(h-1)-1 = 2 \left[2 N(h-2) -1 \right] - 1 $

$\qquad = 2^2 \left[N(h-2) \right] - 2 -1 $

$\qquad = 2^2 \left[2N(h-3) - 1 \right] - 2^1 -1 $

$\qquad = 2^3 \left[N(h-3) \right] -2^2- 2 -1 $

$\qquad \vdots$

$\qquad = 2^{h-1} \left[N(1) \right] - \left[2^{h-2} +\ldots +2^2+ 2^1 +2^0 \right]$

$\qquad = 2^{h-1} \left[2 \right] - \left[2^{h-1} - 1\right]$

$\qquad = 2^{h-1}+1$

8 votes
8 votes

condition given = difference between the number of nodes in the left and right subtrees is at most 2.
   soln --->>
 suppose n(h) represents minimum no of nodes in binary tree of height h
by following the given condition
n(0) = 1
n(1)= 2
n(2)= 3
n(3)= 5
n(4)=9
n(5)=17
n(h)=??
--->> by seeing the above pattern a layman can easily guess that n(h)=2n(h-1) -1 {a recurence relation with base condition n(1)=2 for this}
   an alternate method to find recurence relation 
suppose we have a binary tree with nodes n(h-1) for height h-1 so to build next binary tree of height h we will use tree of height h-1
so that the resultant tree of height h also gives minimum no of nodes
now procedure is starting take a node and make tree of height h-1 {previousely n(h-1)} as left or right sub tree of this root node suppose we are taking this as right sub tree so now this tree is not satisfies our given condition  "difference between the number of nodes in the left and right subtrees is at most 2."
so to we need to add such require no of nodes in left sub tree of root node and this number is determined by the n(h-1) and this number will surely be n(h-1)-2
so RR= n(h)=n(h-1) //for rst +1 //for root + n(h-1)-2 //for lst =2n(h-1)-1  {for h>1}
                   =n(1)=2 {for h=1 it is base condition}
----->>> now our job is to solve recurence relation 
rr = 2n(h-1)-1
    = 2h(n-2) -2 -1
    =2 h(n-3) -22 -2 -1
    =2(h-1) *2-(2(h-2) +2(h-3) ...........-2-1)
    =2h - 2(h-1)+1 =2(h-1) +1

edited by
Answer:

Related questions

27 votes
27 votes
4 answers
1
67 votes
67 votes
2 answers
3
53 votes
53 votes
7 answers
4
Ishrat Jahan asked Nov 3, 2014
13,250 views
The numbers $1, 2, .\dots n$ are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains $p$ nodes. The first number...