Height of binary tree

#1

how is height of a complete binary tree log(n) base2?

#2

hello @sheikhhaji18 the height of the complete binary tree is log(n/0 because it forming the slanting line and not the straight line in the tree.
Let n be the number of nodes in a perfect binary tree and let lk denote the umber of nodes on level
k. Note that:
• lk = 2lk−1, i.e. each level has exactly twice as many nodes as the previous level (since each
internal node has exactly two children)
• l0 = 1, i.e. on the “first level” we have only one node (the root node).
• the leaves are at the last level, lh, where h is the height of the tree.
The total number of nodes in the tree is equal to the sum of the nodes on all the levels: nodes n.
1 + 21 + 22 + 23 + … + 2h = n
From CS 201 we know that 1 + 21 + 22 + 23 + … + 2h = 2h+1 − 1. Therefore:
1 + 21 + 22 + 23 + … + 2h = n
2
h+1 − 1 = n
2
h+1 = n + 1
log2 2
h+1 = log2
(n + 1)
(h + 1) log2 2 = log2
(n + 1)
h + 1 = log2
(n + 1)
h = log2
(n + 1) − 1
Therefore h is O(log n)
if you dont understand anything you can ask here.
Happy Learning !!

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.