GATE 2025 CS2 Q.57: solution and answer

GATE 2025 · CS2Q.57 · 2 marks · NAT

In a B $^{+}$ -tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:

A = (49, 77, 83, -), B = (7, 19, 33, 44), C = (2 0^{*}, 2 2^{*}, 2 5^{*}, 2 6^{*})

The *-marked keys signify that these are data entries in a leaf.

Assume that a pointer between keys $k_{1}$ and $k_{2}$ points to a subtree containing keys in $[k_{1}, k_{2})$ , and that when a leaf is created, the smallest key in it is copied up into its parent.

A record with key value 23 is inserted into the B $^{+}$ -tree.

The smallest key value in the parent of the leaf that contains 25* is ________. (Answer in integer)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The smallest key value in the parent of the leaf containing 25* is 33.

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

Determine the tree structure from the given root-to-leaf path. Root A = (49, 77, 83): all of B's keys (7, 19, 33, 44) are < 49, so B is A's leftmost child (the subtree for keys < 49).
Within B = (7, 19, 33, 44), C's keys (20, 22, 25, 26) all lie in [19, 33), so C is B's child pointer between keys 19 and 33.
Insert key 23 into leaf C. Sorted, the leaf becomes (20, 22, 23, 25, 26) — 5 keys, which exceeds the maximum of 4, so the leaf overflows and must split.
Leaf split (order 4, so 5 entries split as ⌈5/2⌉ = 3 and ⌊5/2⌋ = 2): the left leaf keeps (20, 22, 23); the right leaf keeps (25, 26). Per the stated rule for a newly created leaf, the smallest key of the new right leaf, 25, is copied up into the parent B (the original leaf's key stays as-is; only the new leaf's smallest key is inserted into the parent).
Insert 25 into B in the slot that separates the two split leaves, i.e. between 19 and 33: B becomes (7, 19, 25, 33, 44) — 5 keys, exceeding the maximum of 4, so B (an internal node) also overflows and must split.
Internal-node split (5 keys: 7, 19, 25, 33, 44): the middle key, 25, is pushed up into the parent A and removed from B (an internal-node split pushes the middle key up rather than copying it, unlike a leaf split). The left node keeps (7, 19); the right node keeps (33, 44).
The right half of the split leaf, (25*, 26*), is attached as the child of the new right internal node (the one carrying keys 33, 44), since its keys start at 25.
The parent of the leaf (25*, 26*) is therefore the node with keys (33, 44); its smallest key is 33.

KEY IDEA

Trace the B+-tree insertion as a cascading split: first split the overflowing leaf (copy up the new right leaf's smallest key), then check whether that insertion overflows the parent and split it too (push up the middle key), and finally identify which of the resulting internal nodes the new leaf actually hangs from — the answer is the smallest key in that node, not in the original parent B.

WATCH OUT FOR

Stopping after the leaf split and reporting the value copied up into the (pre-split) parent B — e.g. giving 25, or giving 19 by keeping the leaf attached to the original left-hand side — instead of continuing to split the overflowing internal node B and re-checking which of the two resulting nodes (7,19) or (33,44) the (25*,26*) leaf now belongs to.

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

GATE 2025 CS2 Q.57: solution and answer

Answer and solution

More Trees & heaps questions