GATE CS 2025 Set 2 Q25 — Binary Search Trees

To find the number of edges in the path from the node containing $19$ to the root node, we construct the Binary Search Tree (BST) by inserting the elements one by one in the given order: $10, -4, 15, 30, 20, 5, 60, 19$.

Step-by-Step Insertion:

1. Insert $10$: Root of the tree.

       10
       

2. Insert $-4$: Since $-4 < 10$, insert as the left child of $10$.

         10
        /
      -4
       

3. Insert $15$: Since $15 > 10$, insert as the right child of $10$.

         10
        /  \
      -4    15
       

4. Insert $30$: $30 > 10 \rightarrow 30 > 15$, insert as the right child of $15$.

         10
        /  \
      -4    15
              \
               30
       

5. Insert $20$: $20 > 10 \rightarrow 20 > 15 \rightarrow 20 < 30$, insert as the left child of $30$.

         10
        /  \
      -4    15
              \
               30
              /
            20
       

6. Insert $5$: $5 < 10 \rightarrow 5 > -4$, insert as the right child of $-4$.

          10
         /  \
       -4    15
         \     \
          5     30
               /
             20
       

7. Insert $60$: $60 > 10 \rightarrow 60 > 15 \rightarrow 60 > 30$, insert as the right child of $30$.

          10
         /  \
       -4    15
         \     \
          5     30
               /  \
             20    60
       

8. Insert $19$: $19 > 10 \rightarrow 19 > 15 \rightarrow 19 < 30 \rightarrow 19 < 20$, insert as the left child of $20$.

          10
         /  \
       -4    15
         \     \
          5     30
               /  \
             20    60
            /
           19
       

Path from $19$ to the Root ($10$):

The path from node $19$ to the root node $10$ is:

$$19 \rightarrow 20 \rightarrow 30 \rightarrow 15 \rightarrow 10$$

The number of edges in this path is the number of transitions between nodes, which is:

$$5 \text{ nodes} - 1 = 4 \text{ edges}$$