UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 26)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 26)

Q 26. A binary search tree in which every non-leaf node has non-empty left and right sub-trees is called a strictly binary tree. Such a tree with 19 leaves :

1. cannot have more than 37 nodes
2. has exactly 37 nodes
3. has exactly 35 nodes
4. cannot have more than 35 nodes

 Answer : 2). has exactly 37 nodes

Reason : 

If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one. A strictly binary tree with N leaves always contains 2N – 1 nodes. 

Now we have 19 leaves, Therefore  (2 x 19) - 1 =  38 - 1 = 37