---
title: "Resolving underflow in B-tree"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:btree-underflow-balance-combine"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/btree-underflow-balance-combine
site: BCT Engineering
---

# Resolving underflow in B-tree

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2068 Magh, 5 marks
- Video: [B-Tree Explained | Insertion & Deletion in 4 minutes](https://www.youtube.com/watch?v=ownO77M4SWI) — Baa Code Education
- 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-underflow-balance-combine
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

How can you resolve underflow problem in B-tree? Discuss with reference to balance and combine.

## Short answer

Underflow is resolved by balance (borrow a key from a sibling with more than minimum keys) or combine (merge sibling and parent separator into one node). Balance redistributes keys; combine may reduce tree height.

## Answer

**Underflow** happens in a B-tree of order m when a deletion leaves a non-root node with fewer than the minimum number of keys, ⌈m/2⌉ − 1 (for order 5, fewer than 2 keys). The node is then repaired using an adjacent sibling that has the same parent.

#### 1. Balance (borrow / redistribute / rotate)
Used when an adjacent sibling has more than the minimum number of keys.
1. Move the separator key in the parent down into the underflowing node.
2. Move the nearest key of the rich sibling up to replace the separator in the parent.
3. If the nodes are internal, also move the child pointer that goes with the borrowed key.

Example (order 5, min 2 keys). Delete 10 from:

```text
    [30]                      [40]
   /    \       delete 10    /    \
[10 20] [40 50 60]  ==>   [20 30] [50 60]
```
After the deletion the left leaf is `[20]`, with only 1 key (underflow). The right sibling has 3 keys, so 30 comes down and 40 goes up.

#### 2. Combine (merge / concatenate)
Used when the sibling has exactly the minimum number of keys, so nothing can be borrowed.
1. Merge the underflowing node, the separator key from the parent, and the sibling into one node.
2. Remove the separator and the extra pointer from the parent.
3. The parent may now underflow, so repeat balance or combine upward. If the root loses its last key, the merged node becomes the new root and the tree height decreases by one.

Example. Delete 10 from:

```text
    [30]
   /    \        delete 10
[10 20] [40 50]     ==>      [20 30 40 50]
```
After the deletion `[20]` underflows, and its sibling `[40 50]` has only the minimum 2 keys. Combine `[20]` + 30 + `[40 50]` = `[20 30 40 50]`; the root becomes empty and is removed, so the merged node is the new root.

| Method | When | Effect on parent | Height |
|---|---|---|---|
| Balance | sibling has spare keys | one key replaced | unchanged |
| Combine | sibling at minimum | loses one key | may decrease |

## Check yourself

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

1. In a B-tree of order m, when does underflow occur?
   A. When a node has more than m - 1 keys
   B. When the root is full
   C. When a non-root node has fewer than ceil(m/2) - 1 keys after deletion
   D. When two keys are equal
   Answer: C. For order 5 the minimum is 2 keys, so a node with 1 key underflows. (Key point: Underflow definition)

2. When can underflow be fixed by balance (borrowing)?
   A. When an adjacent sibling has more than the minimum number of keys
   B. When the sibling is empty
   C. Only when the node is the root
   D. Only when the parent has one key
   Answer: A. The node borrows through the parent, so a sibling with spare keys is needed. (Key point: When to balance)

3. How does balancing move keys?
   A. The smallest key of the tree moves to the root
   B. Both siblings are merged into one
   C. The parent's separator key moves down into the node and a key from the rich sibling moves up into the parent
   D. The deleted key is reinserted
   Answer: C. The separator comes down and the nearest sibling key replaces it in the parent; height is unchanged. (Key point: How balance works)

4. When the sibling has exactly the minimum keys, what is done?
   A. Merge the node, the separator and the sibling; the parent loses one key
   B. Borrow from the root
   C. Split the sibling
   D. Delete the sibling
   Answer: A. Combine merges them into one node, may cause parent underflow, and can reduce the height if the root becomes empty. (Key point: Combine)

## Related in Data Structure and Algorithm

- [Queue overflow and underflow errors](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aqueue-overflow-underflow) — Data Structure and Algorithm, chapter 2
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×
- [Tree recursion and TOH with n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atree-recursion-toh-algorithm) — Data Structure and Algorithm, chapter 5
- [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 delete then insert gives same tree?](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-delete-insert-original) — Data Structure and Algorithm, chapter 6

## Related in other subjects

- [Overfitting in ID3 and decision tree rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-overfitting-rules) — Data Mining, chapter 3
- [Reference argument in copy constructor](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Acopy-constructor-reference) — Object Oriented Programming, chapter 4
- [Depreciation, causes; declining balance for 50,000](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Adepreciation-causes-db-50000) — Engineering Economics, chapter 7, asked 2×
- [Monthly deposits, quarterly compounding, balance at year 8](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Aequal-monthly-deposits-balance-8-years) — Engineering Economics, chapter 2