--- title: "B-tree of order 5 for 82, 12, 22, ..." subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:btree-order5-82-12-22" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/btree-order5-82-12-22 site: BCT Engineering --- # B-tree of order 5 for 82, 12, 22, ... Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2075 Baisakh, 5 marks - Video: [Lec-115: Insertion in B-Tree with example in Hindi](https://www.youtube.com/watch?v=YUtUNlLNB5c) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/btree-order5-82-12-22 - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question Construct a B-tree of order 5 for the following data: 82, 12, 22, 23, 56, 96, 37, 99, 59, 74, 28, 65, 60 and 44. ## Short answer Keys inserted sequentially; a node overflows at 5 keys and splits, moving median up. Final tree: root [23 56 82] and leaves [12 22], [28 37 44], [59 60 65 74], [96 99]. ## Answer A B-tree of order 5 allows at most 5 children (4 keys) per node and at least 2 keys in a non-root node. A key is inserted into its leaf; if the leaf then holds 5 keys it overflows, is split at the median, and the median moves up to the parent. The split may repeat up to the root. #### Step-by-step construction | Step | Insert | Tree after step | Action | |---|---|---|---| | 1 | 82 | `[82]` | fits in leaf | | 2 | 12 | `[12 82]` | fits in leaf | | 3 | 22 | `[12 22 82]` | fits in leaf | | 4 | 23 | `[12 22 23 82]` | fits in leaf | | 5 | 56 | `[23]{[12 22], [56 82]}` | leaf [12 22 23 56 82] overflows, split: 23 moves up; new root | | 6 | 96 | `[23]{[12 22], [56 82 96]}` | fits in leaf | | 7 | 37 | `[23]{[12 22], [37 56 82 96]}` | fits in leaf | | 8 | 99 | `[23 82]{[12 22], [37 56], [96 99]}` | leaf [37 56 82 96 99] overflows, split: 82 moves up | | 9 | 59 | `[23 82]{[12 22], [37 56 59], [96 99]}` | fits in leaf | | 10 | 74 | `[23 82]{[12 22], [37 56 59 74], [96 99]}` | fits in leaf | | 11 | 28 | `[23 56 82]{[12 22], [28 37], [59 74], [96 99]}` | leaf [28 37 56 59 74] overflows, split: 56 moves up | | 12 | 65 | `[23 56 82]{[12 22], [28 37], [59 65 74], [96 99]}` | fits in leaf | | 13 | 60 | `[23 56 82]{[12 22], [28 37], [59 60 65 74], [96 99]}` | fits in leaf | | 14 | 44 | `[23 56 82]{[12 22], [28 37 44], [59 60 65 74], [96 99]}` | fits in leaf | #### Final B-tree of order 5 ```text [23 56 82] [12 22] [28 37 44] [59 60 65 74] [96 99] ``` All leaves are on the same level and every node respects the key limits. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How many keys can a node of a B-tree of order 5 hold at most? A. 5 B. 3 C. 2 D. 4 Answer: D. Order m means up to m children and m-1 keys, so 4 keys; the fifth key causes overflow. (Key point: Order 5 limits) 2. Inserting 56 into [12 22 23 82] makes 5 keys. What happens? A. 12 moves up B. Median 23 moves up to a new root; leaves [12 22] and [56 82] C. 82 moves up D. The leaf grows to 5 keys Answer: B. The median of 12 22 23 56 82 is 23, which moves up and creates a new root. (Key point: First split) 3. The leaf [28 37 56 59 74] overflows after inserting 28. Which key moves up? A. 37 B. 59 C. 28 D. 56 Answer: D. The middle (3rd) key of the five is 56, and it joins the root giving [23 56 82]. (Key point: Split moving 56 up) 4. What does the final tree look like? A. Root [23] with two leaves B. Root [23 56 82] with four leaves; all leaves at the same level C. Root [56] with leaves of different depths D. A single node holding all 14 keys Answer: B. The root has 3 keys and 4 children, and B-tree leaves are always on the same level. (Key point: Final structure) ## Close variants set in other exams - [B-tree properties; order 5 for 3, 14, 7, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-properties-order5-3-14) — Data Structure and Algorithm, chapter 6, asked 2× ## Related in Data Structure and Algorithm - [B-tree from 78, 21, 14, 11, 97, 85, 74, 63](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-build-78-21-14) — Data Structure and Algorithm, chapter 6, asked 2× - [Merge sort on 47, 27, 56, 23, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-47-27) — Data Structure and Algorithm, chapter 7 - [AVL tree for 52, 65, 72, 15, 11, 32, 20](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-52-65-72) — Data Structure and Algorithm, chapter 6 - [B-tree of order 5 for letters C N G A H ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-order5-cngahekq) — Data Structure and Algorithm, chapter 6, asked 2× - [B-tree of order 3 for 52, 46, 27, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-order3-52-46-27) — Data Structure and Algorithm, chapter 6 - [Heap sort on 37, 33, 26, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-construct-12-element) — Data Structure and Algorithm, chapter 7 ## Related in other subjects - [Partial r12.3 and multiple R1.23 (0.59, 0.46, 0.77)](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Apartial-multiple-corr-r12-059) — Probability and Statistics, chapter 5, asked 3× - [Chi-square test on 100 random numbers](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Achi-square-uniformity-100-numbers) — Simulation and Modeling, chapter 6 - [Grit chamber for 60 MLD, 0.23 mm](https://www.bctengineer.com/question.md?key=semester_6%2Fsanitary_engineering%3Agrit-60mld-0p23) — Sanitary Engineering, chapter 7, asked 2× - [File size: 60 s, 44.1 KHz, 8-bit stereo](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Aaudio-size-60s-44khz-8bit) — Multimedia System, chapter 2, asked 3×