---
title: "AVL tree for 3, 2, 1, 4, 5, 6, 7, ..."
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:avl-build-3-2-1-4"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-build-3-2-1-4
site: BCT Engineering
---

# AVL tree for 3, 2, 1, 4, 5, 6, 7, ...

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2073 Magh, 4 marks
- Video: [Construct AVL tree for the elements 1,2,3,4,5,6,7,8|AVL Tree Insertion with example](https://www.youtube.com/watch?v=NWe2xmaroLY) — Sudhakar Atchala
- 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/avl-build-3-2-1-4
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Construct an AVL tree for the following sequence of elements: 3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12

## Short answer

The final AVL tree has root 7, left child 4 (left child 2 with left 1 and right 3, right child 6 with left 5), and right child 15 (left child 13 with left 12 and right 14, right 16).

## Answer

Insert each key as in a BST and fix any node whose balance factor becomes ±2 by rotation.

Balance factor of a node = height(left subtree) − height(right subtree). It must stay −1, 0 or +1. After each insertion, find the nearest unbalanced ancestor of the new node and fix it:

| Case | Where the new node went | Fix |
|---|---|---|
| LL | left subtree of left child | single right rotation |
| RR | right subtree of right child | single left rotation |
| LR | right subtree of left child | left rotation on the child, then right rotation |
| RL | left subtree of right child | right rotation on the child, then left rotation |

#### Step-by-step insertion

| Step | Insert | Tree after step (root(left,right)) | Imbalance / rotation |
|---|---|---|---|
| 1 | 3 | `3` | balanced |
| 2 | 2 | `3(2,-)` | balanced |
| 3 | 1 | `2(1,3)` | at 3: LL: right rotate at 3 |
| 4 | 4 | `2(1,3(-,4))` | balanced |
| 5 | 5 | `2(1,4(3,5))` | at 3: RR: left rotate at 3 |
| 6 | 6 | `4(2(1,3),5(-,6))` | at 2: RR: left rotate at 2 |
| 7 | 7 | `4(2(1,3),6(5,7))` | at 5: RR: left rotate at 5 |
| 8 | 16 | `4(2(1,3),6(5,7(-,16)))` | balanced |
| 9 | 15 | `4(2(1,3),6(5,15(7,16)))` | at 7: RL: right at 16, left at 7 |
| 10 | 14 | `4(2(1,3),7(6(5,-),15(14,16)))` | at 6: RL: right at 15, left at 6 |
| 11 | 13 | `7(4(2(1,3),6(5,-)),15(14(13,-),16))` | at 4: RR: left rotate at 4 |
| 12 | 12 | `7(4(2(1,3),6(5,-)),15(13(12,14),16))` | at 14: LL: right rotate at 14 |

#### Final AVL tree

```text
7
├─L:4
│  ├─L:2
│  │  ├─L:1
│  │  └─R:3
│  └─R:6
│     └─L:5
└─R:15
   ├─L:13
   │  ├─L:12
   │  └─R:14
   └─R:16
```

Height = 4, and every node has balance factor −1, 0 or +1.

## Check yourself

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

1. Inserting 1 into 3(2,-) makes 3 unbalanced. Which case and fix?
   A. RR; left rotation at 3
   B. LR; double rotation
   C. RL; double rotation
   D. LL; right rotation at 3
   Answer: D. 1 is in the left subtree of the left child, so rotate right; result 2(1,3). (Key point: Insert 1 into 3(2,-))

2. Inserting 5 into 2(1,3(-,4)) unbalances 3. Fix?
   A. RR; left rotation at 3 giving 4(3,5)
   B. LL; right rotation at 3
   C. RL; double rotation
   D. No fix needed
   Answer: A. 5 goes right of the right child 4, so a left rotation at 3 makes 4 the parent. (Key point: Insert 5)

3. Inserting 15 into ...6(5,7(-,16)) puts it left of 16 under 7. Fix?
   A. RR: left at 7
   B. RL: right at 16, left at 7
   C. LR: left at 16, right at 7
   D. LL: right at 7
   Answer: B. 15 is in the left subtree of the right child, so a double RL rotation is used. (Key point: Insert 15)

4. What is the root and height of the final AVL tree?
   A. Root 3, height 12
   B. Root 4, height 3
   C. Root 7, height 4
   D. Root 16, height 5
   Answer: C. The final tree is 7(4(...),15(...)) with height 4. (Key point: Final tree)

## Related in Data Structure and Algorithm

- [AVL tree for 24, 12, 8, 15, 35, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-24-12-8) — Data Structure and Algorithm, chapter 6
- [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
- [AVL tree for 10 20 30 50 45 40 8 5 3](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30) — Data Structure and Algorithm, chapter 6
- [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×
- [AVL tree for month names](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-months) — Data Structure and Algorithm, chapter 6, asked 2×
- [B-tree insertion algorithm; AVL of months](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-insertion-avl-months) — Data Structure and Algorithm, chapter 6, asked 2×

## Related in other subjects

- [K-map Σm(7,9,12,13,14,15)+d, NOR-only](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Akmap-nor-sum-7-9-12) — Digital Logic, chapter 3
- [Minterms/maxterms; K-map Σm(0,1,2,4,6,8,9,12,13,14)](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Aminterm-maxterm-kmap-01246) — Digital Logic, chapter 3
- [32:1 MUX tree; implement Σm(0,1,3,8,9,13,15)](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-32to1-tree-function-15) — Digital Logic, chapter 4
- [Standard error; population 12,19,13,16](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Astandard-error-population-12-19-13) — Probability and Statistics, chapter 4