---
title: "AVL tree for 10 20 30 50 45 40 8 5 3"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:avl-build-10-20-30"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-build-10-20-30
site: BCT Engineering
---

# AVL tree for 10 20 30 50 45 40 8 5 3

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2074 Bhadra, 6 marks
- Video: [Avl tree insertion || inserting elements into the avl  tree](https://www.youtube.com/watch?v=l2kug-ZBqaM) — LEARN DS FAST 
- 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-10-20-30
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Create an AVL balanced tree for data sequence 10 20 30 50 45 40 8 5 3.

## Short answer

After insertions with rotations, the final AVL tree has root 30, left child 10 (left child 5 with left 3 and right 8, right child 20), and right child 45 (left 40, right 50). All balance factors are -1,0,+1.

## Answer

Insert the keys one by one like in a BST, then rebalance with rotations whenever a balance factor becomes ±2.

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 | 10 | `10` | balanced |
| 2 | 20 | `10(-,20)` | balanced |
| 3 | 30 | `20(10,30)` | at 10: RR: left rotate at 10 |
| 4 | 50 | `20(10,30(-,50))` | balanced |
| 5 | 45 | `20(10,45(30,50))` | at 30: RL: right at 50, left at 30 |
| 6 | 40 | `30(20(10,-),45(40,50))` | at 20: RL: right at 45, left at 20 |
| 7 | 8 | `30(10(8,20),45(40,50))` | at 20: LL: right rotate at 20 |
| 8 | 5 | `30(10(8(5,-),20),45(40,50))` | balanced |
| 9 | 3 | `30(10(5(3,8),20),45(40,50))` | at 8: LL: right rotate at 8 |

#### Final AVL tree

```text
30
├─L:10
│  ├─L:5
│  │  ├─L:3
│  │  └─R:8
│  └─R:20
└─R:45
   ├─L:40
   └─R:50
```

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. How is the balance factor of a node defined, and what values are allowed?
   A. height(left) - height(right); -1, 0 or +1
   B. height(right) + height(left); 0 or 1
   C. number of nodes left minus right; any value
   D. height(left) x height(right); 1 only
   Answer: A. AVL requires subtree heights to differ by at most 1. (Key point: Balance factor)

2. Inserting 30 into 10(-,20) makes 10 unbalanced. Which case and fix?
   A. LL; right rotation at 10
   B. RR; left rotation at 10
   C. RL; double rotation
   D. LR; double rotation
   Answer: B. 30 goes to the right subtree of the right child, so a single left rotation gives 20(10,30). (Key point: Rotation for 10, 20, 30)

3. Inserting 45 into 20(10,30(-,50)) puts it left of 50. Which fix is used at 30?
   A. RR: left rotation at 30
   B. LR: left at 50 then right at 30
   C. RL: right rotation at 50, then left rotation at 30
   D. LL: right rotation at 30
   Answer: C. 45 lies in the left subtree of the right child, so RL double rotation gives 20(10,45(30,50)). (Key point: Double rotation)

4. What is the root and height of the final AVL tree for 10 20 30 50 45 40 8 5 3?
   A. Root 10, height 9
   B. Root 20, height 3
   C. Root 45, height 5
   D. Root 30, height 4
   Answer: D. After all rotations the tree is 30(10(5(3,8),20),45(40,50)) with height 4. (Key point: Final tree)

## Related in Data Structure and Algorithm

- [AVL tree for 10, 20, 30, 35, 50, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30-35) — Data Structure and Algorithm, chapter 6
- [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 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×
- [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

- [Elliptic: 2x2 grid 10/20/40/50](https://www.bctengineer.com/question.md?key=semester_4%2Fnumerical_method%3Aelliptic-2x2-10-20-40-50) — Numerical Method, chapter 7, asked 5×