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?

Solution

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

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

Solution

Answer=21 null branches
If the tree has 3 nodes then it has 4 null branches.ie 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?
Solution

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)?
Solution