GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
39 views
Why is $n \leq 2^{h+1} - 1$ equivalent to $h \geq \log_2{\frac{n+1}{2}}$ ? This is applicable to Binary Trees
asked in Graph Theory by (305 points)   | 39 views

1 Answer

+1 vote
Best answer

This is a basic concept for calculating minimum height for Binary Trees.

Hope you know A Complete Binary tree corresponds to maximum possible number of nodes in any tree.

When Nodes are maximum (Fully dense tree) then this also corresponds to minimum hight of the tree.

Now lets derive the formula

At level 0 Number of nodes possible --------->>>>> 1 (Root)     // 20

At level 1 Number of nodes possible--------->>>>>2                 //  21

At level 2 Number of nodes possible--------->>>>>4                //  22

At level 3 Number of nodes possible--------->>>>>8               //  23

At level 4 Number of nodes possible--------->>>>>16             //  24

so Ultimately we can generalize it like at Level H (height) Number of nodes possible--------->>>>> 2H

So to know total possible number of nodes add the maximum possible nodes at each individual level

Total number of possible nodes in level 'H' binary tree ---->>> 20+21+22+23+24.....+2H

So maximum nodes possible would be 2h+1-1

so n<= 2h+1-1 Now the log work you can do..

answered by Active (1.8k points)  
selected by
How do u get the log?

Basic log calculation

n<= 2h+1-1

so n+1 <=2h+1

take log both side

log (n+1) <=h+1

so h>=log2(n+1)-1  ; // log22=1  ; log a/b= log a - log b

so h>= log2 ( (n+1)/2 )



Top Users Aug 2017
  1. Bikram

    5174 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3504 Points

  4. manu00x

    3492 Points

  5. rahul sharma 5

    3188 Points

  6. makhdoom ghaya

    2700 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2090 Points

  10. pawan kumarln

    1874 Points


25,065 questions
32,220 answers
75,083 comments
30,231 users