308 views

1 Answer

Best answer
1 votes
1 votes

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..

selected by

Related questions

0 votes
0 votes
0 answers
1
srestha asked Apr 1, 2019
313 views
Can somebody explainWhat is identity permutation?
0 votes
0 votes
0 answers
2
srestha asked Apr 20, 2018
420 views
What is value of $\log _{2}10$?In general calculator $\ln _{2}10$ is giving 2.3....But it should be 3. somethingright?
0 votes
0 votes
0 answers
3
srestha asked Sep 25, 2018
506 views
$1)$ Is there any general formula for maximum degree (if possible also minimum degree) of a vertex in a graph G?$2)$ Is there any relationship between indegree and outdeg...
0 votes
0 votes
1 answer
4
Çșȇ ʛấẗẻ asked Sep 14, 2023
113 views