GATE CS 2004 Q4 — Binary Search Trees

We construct the Binary Search Tree (BST) by inserting the elements one by one according to the BST property (smaller elements to the left, larger elements to the right):

1. 10 becomes the root.
2. 1 is less than 10, so it goes to the left of 10.
3. 3 is less than 10 but greater than 1, so it goes to the right of 1.
4. 5 is less than 10, greater than 1, and greater than 3, so it goes to the right of 3.
5. 15 is greater than 10, so it goes to the right of 10.
6. 12 is greater than 10 but less than 15, so it goes to the left of 15.
7. 16 is greater than 10 and greater than 15, so it goes to the right of 15.

The resulting tree structure is:

       10
      /  \\
     1    15
      \\   / \\
       3 12  16
        \\
         5

The height of the tree is the maximum number of edges from the root to any leaf node. The longest path is $10 \rightarrow 1 \rightarrow 3 \rightarrow 5$, which consists of $3$ edges. Thus, the height of the tree is $3$.