IAE Academy

GATE 2026 DA Q.41: solution and answer

GATE 2026 · DAQ.41 · 2 marks · MCQ

Consider a B+ Tree where the maximum number of key values in each leaf node is 2 and the maximum number of pointers in each non-leaf node is 3. Let the content of the B+ Tree be as shown in the figure.

Which of the following options denotes the key value(s) stored in the root node after inserting a key value 3 in the given B+ Tree?

GATE 2026 DA question 41: A B+ tree.Tap to open full size
Figure from the GATE 2026 DA paper. It is part of the question.
Figure description

A B+ tree. The root (non-leaf) node holds keys 5 and 8 with three child pointers: left, middle and right. The left pointer goes to leaf [1, 5], the middle pointer to leaf [7, 8], the right pointer to leaf [9, 12]. The leaves are chained left to right by sibling pointers (the last leaf's next pointer is NULL). Each key in a leaf has a dashed downward arrow to its record. Following the figure, keys less than or equal to 5 are under the left pointer (leaf [1, 5] contains 5), keys from 6 to 8 under the middle pointer (leaf [7, 8]) and keys above 8 under the right pointer (leaf [9, 12]).

  1. (A)

    5

  2. (B)

    8

  3. (C)

    3 and 5

  4. (D)

    3, 5 and 8

Answer and solution

ANSWER

The root stores only the key 5, which is option (A).

Official answer: ASource: Official answer key, GATE 2026 DA (IIT Guwahati)

  1. Each non-leaf node holds at most 3 pointers, so at most 2 keys. Each leaf holds at most 2 keys. In the figure the separator 5 sits above a leaf that contains 5 (), and the separator 8 sits above a leaf that contains 8 (). So keys a separator lie in the subtree to its left.

  2. The key 3 is , so it goes into the leftmost leaf . The leaf would become with 3 keys, which exceeds the limit of 2, so the leaf splits.

  3. Split the leaf into and . In a B+ tree the separator is copied up and stays in the leaf. With the keys separator convention the separator is 3, the largest key of the left leaf.

  4. The root would now hold keys with 4 child pointers. This is more than the 3 pointers allowed, so the root overflows and splits.

  5. Splitting a non-leaf node moves the middle key up instead of copying it. The 4 pointers divide 2 and 2. The middle key 5 moves up. The left internal node holds key 3 with children and . The right internal node holds key 8 with children and .

  6. The new root holds the single key 5. If the leaf were split as and instead, the copied-up separator would be 1, the root would briefly hold , and the middle key would still be 5. So the root is under either split, and the answer is (A).

KEY IDEA

A leaf split copies the separator up and keeps it in the leaf. A non-leaf split moves the middle key up. Here the inserted 3 overflows the leaf, which makes the root overflow, and the middle key 5 becomes the new root.

WATCH OUT FOR

Stopping after the leaf split and concluding the root is or (options D or C). With at most 3 pointers per non-leaf node, 3 keys and 4 pointers cannot stay in one node, so the root must split too. Another mistake is to copy the middle key up from the internal node instead of moving it, which would leave 5 duplicated in the internal level.

From the GATE 2026 DA paper. Every question of this paper · Download the full paper · All 3 Indexing questions, with notes