edited by
22,472 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

2 votes
2 votes

Just mentioning another approach to solve this problem. 

If anything is not proper then please notify. I hope this helps. 

edited by
0 votes
0 votes

Option  B is correct.

Let m(h) denotes the minimum number of nodes required for height h. 

Then the required recursive equation will be :

min nodes in height h = {min nodes in left sub-tree with height h-1} + {(min nodes in left sub-tree with height h-1) – 2} + {root node}

m(h) = {m(h-1)} + {m(h-1) – 2} + {1}.

m(h) = 2 * m(h-1) – 1

Base condition : m(h==1) = 2

m(h) = 2^k * m(h-k) – (2^k -1)

let k = h-1 for base condition.

m(h) = 2^(h-1) +1

 

–3 votes
–3 votes

Wrong options

reshown by
Answer:

Related questions

27 votes
27 votes
4 answers
5
67 votes
67 votes
2 answers
7
53 votes
53 votes
7 answers
8
Ishrat Jahan asked Nov 3, 2014
13,292 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...