IAE Academy

GATE 2025 CS1 Q.21: solution and answer

GATE 2025 · CS1Q.21 · 1 mark · MSQ

Consider the following tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the tree. Which of the following options(s) is/are CORRECT?

GATE 2025 CS1 question 21: A B^+ tree with 5 nodes.Tap to open full size
Figure from the GATE 2025 CS1 paper. It is part of the question.
Figure description

A B^+ tree with 5 nodes. The root holds keys 6, 12, 19. It has four children, all leaves, left to right: [1, 4, 3] (as printed), [7, 9, 10], [13, 15, 17], [20, 21, 22]. Each leaf holds 3 keys, so every node is full.

  1. (A)

    None of the nodes will split.

  2. (B)

    At least one node will split and redistribute.

  3. (C)

    The total number of nodes will remain same.

  4. (D)

    The height of the tree will increase.

Answer and solution

ANSWER

Options (B) and (D) are correct.

Official answer: B, DSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

  1. Each node holds at most 3 keys. The root and all four leaves , , , are full.

  2. Search for 23. Since , it belongs in the rightmost leaf , which is already full.

  3. Insert 23 there. The leaf overflows to and splits into and . In a tree the first key of the new right leaf, 22, is copied up to the parent.

  4. The parent is the root , which is also full. Adding 22 gives with five children, so the root overflows and splits too.

  5. The internal split keeps (children , , ) and (children , ). The middle key 19 moves up (not copied) into a new root .

  6. Count the nodes. Before: 5. After: one new leaf, one new internal node and one new root, so . The height goes from 2 levels to 3.

  7. Check each option. (A) False, since the leaf and the root split. (B) True, since at least one node splits. (C) False, since the count rises from 5 to 8. (D) True, since a new root was created.

KEY IDEA

When a leaf overflows, it splits and copies a key up. If every ancestor up to the root is full, the splits cascade and a new root is made, so the height grows by one.

WATCH OUT FOR

Stopping after the leaf split and forgetting that the parent is also full. That leads to choosing (C), or to choosing (A) because only one node seems to split.

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 9 Indexing questions, with notes

More Indexing questions