GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
48 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 (325 points) 2 6 16 | 48 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 Boss (5.1k points) 7 20
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 )



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23438 Points

  2. Bikram

    17108 Points

  3. Habibkhan

    8354 Points

  4. srestha

    6314 Points

  5. Debashish Deka

    5458 Points

  6. jothee

    5008 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4390 Points

  9. sushmita

    3996 Points

  10. Rishi yadav

    3840 Points


Recent Badges

Popular Question sunil sarode
Verified Human nandisrinivas
Nice Question shraddha priya
Popular Question just_bhavana
Famous Question rahul sharma 5
Popular Question Jithin Jayan
Great Answer Sankaranarayanan P.N
Good Question jothee
Great Answer Sankaranarayanan P.N
Famous Question pC
27,346 questions
35,200 answers
84,230 comments
33,327 users