Properties Of Binary Trees

Trees are non linear data structures mostly used for hierarchical representation.
A binary tree is a tree in which every node will have at most two children. Before going to the properties of such binary trees,let us see two important types of binary trees.

Complete Binary Tree

It is the binary tree in which all levels except the last,is completely filled and all the nodes are as far left as possible.

Example 

       

                 
               


Almost Complete Binary Tree

A binary tree is said to be almost complete binary tree when all the leaves of the tree are either at d or d-1 level.here, d is the depth of the tree.

Example

       

Properties of Binary Trees

1.The maximum number of nodes for a complete binary tree with height h is 2^h+1 -1

Example

     

 Here,this is a complete binary tree with height=2          
   then the max no. of nodes=22+1 -1 =>7
            

2.For a complete binary tree or almost complete binary tree,if n are the number of nodes then the  height of tree is ceil(log n).

Example 1

           

 Here this is a complete binary tree and number of nodes are 3
therefore,the height of the tree is ceil(log 3) =1

Example 2

 Here this is an almost complete binary tree and number of nodes are 5
therefore,the height of the tree is ceil(log 5) =2

3.For a complete binary tree or almost complete binary tree,the starting of leaf nodes is from [n/2]+1 to n.

               

Example 1

  

Here,this is a complete binary tree and has 7 nodes
therefore,the starting of the leaf nodes is from [7/2]+1 to 7= 4 to 7

 Example 2

     








Here,this is an almost complete binary tree and has 5 nodes
therefore,the starting of the leaf nodes is from [5/2]+1 to 5= 3 to 5

4.The no. of leaf nodes for a binary tree with n nodes and  having 0 or 2 children is (n+1)/2

Example 1

The number of leaf nodes =(7+1)/2
                                          =4    
5.For any binary tree,the maximum number of nodes at level 'l' is 2^l-1

Example

At level 1, the maximum number of nodes=2^(1-1) =2⁰ =1    

At level 2,the maximum number of nodes=2^(2-1) =2¹ =2   
At level 3,the maximum number of nodes=2^(3-1) = 2² =4

6.In a binary tree number of leaf nodes is always one more than nodes with two children

Example

Here the number of nodes with two children=2

Therefore,number of leaf nodes=2+1=3