The greatest mistake you can make in life is to be continually fearing you will make one

Sunday, 14 March 2010

Problems based on Binary Tree

1.A strictly binary tree contains 10 leaves(nodes dont have children). find the total number of nodes in the tree?


Total number of nodes=19
A strictly binary tree with n leaves always contains 2n-1 the tree has 2*10-1 ie 19 nodes

2.A binary tree has 20 nodes. Then how many null branches have the tree?

Answer=21 null branches
If the tree has 3 nodes then it has 4 null 3+1. If the tree has 5 nodes then it has 6 null branches.ie5+1. In general a binary tree with n nodes has exactly n+1 null nodes. So 20 nodes has 21 null branches.

3.In the given binary tree below, in which location the node 4 is stored in an array?
Solution:The node 4 is stored at location 6.
The nodes are stored in the array in the order of root first then left child of root,right child of root, then left child of child1,right child of child1,then left child of child2 ,right child of child 2 and so on.
Here LCn means left child of node n and RCn means right child of node n.
In array the index starts from 0. so the node 4 is at location 6. but the index value is 5.

4.Comparing to Incomplete Binary Tree,Complete Binary Tree and Full Binary Tree,Which tree is efficient considering space and time complexities?

Complete Binary Tree
Full binary tree loses its nature when operationas of insertions and deletions are done. For Incomplete Binary trees extra storage is required and overhead of NULL node checking takes place. So complete binary tree is the better one since the property of complete binary tree is maintained even after operations like additions and deletions are done on it.

5.Draw a Binary Tree for the expression A*B-(C+D)*(P/Q)?



  1. Array representation
    Suppose T is a binary tree that is complete or nearly complete or nearly complete. Then there is an efficient representation of T. This representation uses only a single linear arrayRead more
    Check this siteTeKslate for indepth DataStructures training.
    Go here if you’re looking for information on DataStructures training.