---
title: "B-tree of order 5 for letters C N G A H ..."
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:btree-order5-cngahekq"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/btree-order5-cngahekq
site: BCT Engineering
---

# B-tree of order 5 for letters C N G A H ...

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2072 Asoj, 6 marks
- Video: [5.26 Insertion in B-Tree of Order 5 with Given Alphabets | Data structures and algorithms](https://www.youtube.com/watch?v=asRbo5HWpxc) — Jenny's Lectures CS IT
- 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-cngahekq
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Construct B-tree of order 5 for the set of data C N G A H E K Q M F W L T Z D P R X Y S showing each step.

## Short answer

Construct by sequential insertion; overflow at 5 keys, split median up. Final tree: root [M], internal nodes [D G] and [Q T], leaf nodes [A C], [E F], [H K L], [N P], [R S], [W X Y Z].

## Answer

Order 5 means at most 4 keys per node and at least 2 keys in a non-root node. Letters are compared alphabetically. When a node reaches 5 keys it is split at the median (3rd key), which moves up.

#### Step-by-step construction

| Step | Insert | Tree after step | Action |
|---|---|---|---|
| 1 | C | `[C]` | fits in leaf |
| 2 | N | `[C N]` | fits in leaf |
| 3 | G | `[C G N]` | fits in leaf |
| 4 | A | `[A C G N]` | fits in leaf |
| 5 | H | `[G]{[A C], [H N]}` | leaf [A C G H N] overflows, split: G moves up; new root |
| 6 | E | `[G]{[A C E], [H N]}` | fits in leaf |
| 7 | K | `[G]{[A C E], [H K N]}` | fits in leaf |
| 8 | Q | `[G]{[A C E], [H K N Q]}` | fits in leaf |
| 9 | M | `[G M]{[A C E], [H K], [N Q]}` | leaf [H K M N Q] overflows, split: M moves up |
| 10 | F | `[G M]{[A C E F], [H K], [N Q]}` | fits in leaf |
| 11 | W | `[G M]{[A C E F], [H K], [N Q W]}` | fits in leaf |
| 12 | L | `[G M]{[A C E F], [H K L], [N Q W]}` | fits in leaf |
| 13 | T | `[G M]{[A C E F], [H K L], [N Q T W]}` | fits in leaf |
| 14 | Z | `[G M T]{[A C E F], [H K L], [N Q], [W Z]}` | leaf [N Q T W Z] overflows, split: T moves up |
| 15 | D | `[D G M T]{[A C], [E F], [H K L], [N Q], [W Z]}` | leaf [A C D E F] overflows, split: D moves up |
| 16 | P | `[D G M T]{[A C], [E F], [H K L], [N P Q], [W Z]}` | fits in leaf |
| 17 | R | `[D G M T]{[A C], [E F], [H K L], [N P Q R], [W Z]}` | fits in leaf |
| 18 | X | `[D G M T]{[A C], [E F], [H K L], [N P Q R], [W X Z]}` | fits in leaf |
| 19 | Y | `[D G M T]{[A C], [E F], [H K L], [N P Q R], [W X Y Z]}` | fits in leaf |
| 20 | S | `[M]{[D G]{[A C], [E F], [H K L]}, [Q T]{[N P], [R S], [W X Y Z]}}` | leaf [N P Q R S] overflows, split: Q moves up; internal node [D G M Q T] overflows, split: M moves up; new root |

#### Final B-tree of order 5

```text
[M]
[D G]  [Q T]
[A C]  [E F]  [H K L]  [N P]  [R S]  [W X Y Z]
```
Tree height is 3 levels (root, one internal level, leaves).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In an order 5 B-tree, which key moves up when a node holds 5 keys?
   A. The smallest key
   B. The largest key
   C. The median (3rd key)
   D. The first key inserted
   Answer: C. A node is split at the median, which moves up to the parent. (Key point: Median choice)

2. Inserting H into [A C G N] gives [A C G H N]. What is the result?
   A. G moves up as new root with leaves [A C] and [H N]
   B. C moves up
   C. H moves up
   D. N moves up
   Answer: A. The 3rd key G is the median, creating a new root. (Key point: First split)

3. The leaf [N Q T W Z] overflows. Which key moves into the parent?
   A. Q
   B. W
   C. T
   D. N
   Answer: C. Median of N Q T W Z is T, giving parent [G M T] and leaves [N Q] and [W Z]. (Key point: Leaf split at Z)

4. When S is inserted, how does the tree grow in height?
   A. The leaf splits (Q up), the internal node [D G M Q T] overflows and splits (M up), and a new root is created
   B. Only the leaf splits
   C. The leaf is merged with its sibling
   D. The root is deleted
   Answer: A. A split can propagate up to the root; since the root overflowed, a new root [M] is created and height becomes 3 levels. (Key point: Cascading split)

## Close variants set in other exams

- [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×

## Related in Data Structure and Algorithm

- [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
- [B-tree of order 5 for 82, 12, 22, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-order5-82-12-22) — Data Structure and Algorithm, chapter 6, asked 2×
- [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×
- [Expression tree and traversals](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aexpression-tree-traversal) — Data Structure and Algorithm, chapter 6
- [Box trace and TOH recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abox-trace-toh-tree) — Data Structure and Algorithm, chapter 5
- [AVL tree for 3, 2, 1, 4, 5, 6, 7, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-3-2-1-4) — Data Structure and Algorithm, chapter 6

## Related in other subjects

- [FP-tree on HotDogs data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-hotdogs) — Data Mining, chapter 4
- [FP-tree on t1-t5 data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-t1-t5) — Data Mining, chapter 4
- [First-order system impulse and step response](https://www.bctengineer.com/question.md?key=semester_4%2Fsignals_and_systems%3Afirst-order-system-response) — Signals and Systems, chapter 5
- [Impulse and ramp response from first order step response](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Afirst-order-impulse-ramp) — Control Systems, chapter 3