GATE CS 1996 Q2.14 — Binary Search Trees

In a Binary Search Tree (BST), the first element inserted becomes the root node. For any subsequent element:

• If it is smaller than the root, it is placed in the left subtree.
• If it is larger than the root, it is placed in the right subtree.

The given insertion sequence is:

$$\{50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24\}$$

Here, the first element is $50$, which becomes the root of the BST.

Now, we partition the remaining elements based on their relation to the root ($50$):

1. Left Subtree: Elements less than $50$ $$\{15, 5, 20, 3, 8, 37, 24\}$$

   Total number of nodes in the left subtree = $7$

2. Right Subtree: Elements greater than $50$ $$\{62, 58, 91, 60\}$$

   Total number of nodes in the right subtree = $4$

Thus, the number of nodes in the left and right subtrees of the root respectively is $(7, 4)$.