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 = (20*, 22*, 25*, 26*)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys k1 and k2 points to a subtree containing keys in [k1,k2], and that when a leaf is created, the smallest key in it is copied up into A. 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 ______.
Solution :
The correct answer is 33.
Step-by-Step Explanation:
1. Initial State of the B+ Tree:
We are given the following path from root to leaf:
- Root node A = (49, 77, 83, –)
- Internal node B = (7, 19, 33, 44)
- Leaf node C = (20*, 22*, 25*, 26*)
Note that leaf node C is currently full because it contains four key values, which is the maximum limit per node.
2. Inserting Key 23:
When a record with key value 23 is inserted, it must be placed in leaf node C because 20 < 23 < 26. This temporarily creates an overfull leaf node containing 5 keys: (20*, 22*, 23*, 25*, 26*).
3. Splitting Leaf Node C:
To resolve the overflow, leaf node C is split into two leaf nodes:
- Left leaf C1 = (20*, 22*, 23*)
- Right leaf C2 = (25*, 26*) (which contains 25*)
Following B+ tree insertion rules, the smallest key of the new right leaf C2 (which is 25) is copied up to the parent internal node B.
4. Splitting Internal Node B:
With the entry 25 copied up, the parent node B now contains 5 keys: (7, 19, 25, 33, 44). Since this exceeds the maximum limit of 4 keys, internal node B must split:
- The middle key (25) is pushed up to the root node A.
- The remaining keys are split into two internal nodes:
• Left internal node B1 = (7, 19)
• Right internal node B2 = (33, 44)
5. Identifying the Parent of Leaf C2:
The pointer corresponding to the range [25, 33] resides in the right split internal node B2 = (33, 44). Therefore, the leaf node containing 25* (which is C2) becomes a child of B2.
The keys present in the parent node B2 are (33, 44), making the smallest key value in this parent node 33.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.