IAE Academy

GATE 2025 CS2 Q.35: solution and answer

GATE 2025 · CS2Q.35 · 1 mark · NAT

Suppose the values are inserted in that order into an initially empty binary search tree. Let be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of is ___________. (Answer in integer)

See the question in the paper
GATE 2025 CS2 question 35Tap to open full size

Answer and solution

ANSWER

The number of edges in the path from the node containing 19 to the root is 4.

Official answer: 4Source: Official answer key, GATE 2025 CS2 (IIT Roorkee)

  1. Insert 10 as the root.

  2. Insert -4: compare with 10 (-4<10) → becomes left child of 10.

  3. Insert 15: compare with 10 (15>10) → becomes right child of 10.

  4. Insert 30: compare with 10 (30>10, go right to 15), then with 15 (30>15) → becomes right child of 15.

  5. Insert 20: compare with 10 (go right to 15), with 15 (go right to 30), with 30 (20<30) → becomes left child of 30.

  6. Insert 5: compare with 10 (5<10, go left to -4), with -4 (5>-4) → becomes right child of -4.

  7. Insert 60: compare with 10 (go right to 15), with 15 (go right to 30), with 30 (60>30) → becomes right child of 30.

  8. Insert 19: compare with 10 (go right to 15), with 15 (go right to 30), with 30 (19<30, go left to 20), with 20 (19<20) → becomes left child of 20.

  9. Path from 19 to the root: 19 → 20 → 30 → 15 → 10 — this path has 4 edges.

KEY IDEA

Standard BST insertion: each new key is compared against nodes starting from the root, going left if smaller and right if larger, until an empty spot is found; the depth of a node equals the number of edges on its unique root path.

WATCH OUT FOR

Counting the number of nodes on the path (5) instead of the number of edges (4), or inserting 5 relative to 10 instead of continuing the BST search down to -4's subtree (5 must be compared against -4, since 5 < 10 sends it left first).

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

More Trees & heaps questions