Skip to main content

AVL tree for 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.

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

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:

CaseWhere the new node wentFix
LLleft subtree of left childsingle right rotation
RRright subtree of right childsingle left rotation
LRright subtree of left childleft rotation on the child, then right rotation
RLleft subtree of right childright rotation on the child, then left rotation

Step-by-step insertion

StepInsertTree after step (root(left,right))Imbalance / rotation
11010balanced
22010(-,20)balanced
33020(10,30)at 10: RR: left rotate at 10
45020(10,30(-,50))balanced
54520(10,45(30,50))at 30: RL: right at 50, left at 30
64030(20(10,-),45(40,50))at 20: RL: right at 45, left at 20
7830(10(8,20),45(40,50))at 20: LL: right rotate at 20
8530(10(8(5,-),20),45(40,50))balanced
9330(10(5(3,8),20),45(40,50))at 8: LL: right rotate at 8

Final AVL tree

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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →