Prove that in a binary tree with n elements the hight of the

Prove that in a binary tree with n elements, the hight of the tree is greater than or equal to [log_2(n)]. Prove that in a complete binary tree with n elements, the hight of the tree is exactly [log_2(n)].

Solution

Binary tree is a tree with the propery that each node has atmost 2 children. so it means either 0 or 2.

depth of a node is defined as length of path from root to that node.

Maximum depth of a binary tree is equal to height of the tree.

The maximum number of nodes that we can have at some level i will be equal to 2 to the power of i. ie; i=2ⁱ

At level 0maximum number of nodes is 2⁰ is 1

At level 1 maximum number of nodes is 2¹ is 2

.

.

..

....

At level h maximum number of nodes is 2^h

h is the height of the binary tree

ie; 2⁰ + 2¹ + 2² ......... +2^h

=> 2^h+1 - 1

n is the number of nodes in a Binary Tree then n=2^h+1 -1

Because if height is h number of nodes will be 2 to the power of (h+1)

2^h+1 = n+1

h=log₂^{(n+1) - 1}

log₂^n.

A perfect Binary tree is always a complete Binary tree.