An AVL tree is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees (Balance Factor) cannot be more than one for all nodes.

What is a Balance Factor?

The Balance Factor of a node is the height of its left subtree minus the height of its right subtree. It must be -1, 0, or 1 in a valid AVL tree.

AVL trees are always balanced, ensuring O(log n) performance for all operations, unlike standard BSTs which can become skewed and O(n).

AVL Tree

An AVL tree is a self-balancing binary search tree in which the heights of the left and right subtrees of every node differ by at most one.

READY

Insert values to watch the tree rebalance. Each node shows its balance factor — left height minus right height — which an AVL tree keeps within ±1.

Value

Intuition

A self-balancing Binary Search Tree (BST) named after its inventors Adelson-Velsky and Landis. It maintains O(log n) height by automatically performing rotations during insertion and deletion if the tree becomes unbalanced.

Concept

In a normal BST, skewed data (like 1, 2, 3, 4...) can degrade performance to O(n). AVL Trees fix this by tracking a Balance Factor (Left Height - Right Height) for every node. If |BF| > 1, it rotates to restore balance.

How it Works

Balance Factor (BF): Height(Left) - Height(Right).
Valid BF: -1, 0, 1.
Rotations: Operations to fix imbalance:
- LL Cases: Right Rotation.
- RR Cases: Left Rotation.
- LR Cases: Left then Right Rotation.
- RL Cases: Right then Left Rotation.

Step-by-Step Breakdown

Insertion Logic:

Insert node like standard BST.
Backtrack up to root, updating heights.
Check Balance Factor of each node.
If Node becomes unbalanced (|BF| > 1):
- Left-Left (LL): Perform Right Rotation.
- Right-Right (RR): Perform Left Rotation.
- Left-Right (LR): Left Rotate left child, then Right Rotate current.
- Right-Left (RL): Right Rotate right child, then Left Rotate current.

When to Use

Database indexing where lookups must be fast O(log n).
Symbol tables in compilers.
When search operations are more frequent than insertions/deletions.

When NOT to Use

When insertions/deletions are very frequent (Red-Black trees might be slightly better due to fewer rotations).
Simple scenarios where O(n) worst case is acceptable.

How to Identify

Key requirements: "Balanced BST", "Guaranteed O(log n) search", "Rotations".

Sample Problems

Convert Sorted List to Binary Search Tree

Create a height-balanced BST.

Balance a Binary Search Tree

Convert an unbalanced BST to a balanced one.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Binary Search Tree

Trie (Prefix Tree)

Complexity

Time (Best)

O(log n)

Time (Average)

O(log n)

Time (Worst)

O(log n)

Space

O(n)

AVL Tree Code

1class Node {
2    constructor(key) {
3        this.key = key;
4        this.left = null;
5        this.right = null;
6        this.height = 1;
7    }
8}
9
10class AVLTree {
11    height(N) {
12        if (!N) return 0;
13        return N.height;
14    }
15
16    max(a, b) {
17        return (a > b) ? a : b;
18    }
19
20    rightRotate(y) {
21        let x = y.left;
22        let T2 = x.right;
23        x.right = y;
24        y.left = T2;
25        y.height = this.max(this.height(y.left), this.height(y.right)) + 1;
26        x.height = this.max(this.height(x.left), this.height(x.right)) + 1;
27        return x;
28    }
29
30    leftRotate(x) {
31        let y = x.right;
32        let T2 = y.left;
33        y.left = x;
34        x.right = T2;
35        x.height = this.max(this.height(x.left), this.height(x.right)) + 1;
36        y.height = this.max(this.height(y.left), this.height(y.right)) + 1;
37        return y;
38    }
39
40    getBalance(N) {
41        if (!N) return 0;
42        return this.height(N.left) - this.height(N.right);
43    }
44
45    insert(node, key) {
46        if (!node) return new Node(key);
47
48        if (key < node.key) node.left = this.insert(node.left, key);
49        else if (key > node.key) node.right = this.insert(node.right, key);
50        else return node;
51
52        node.height = 1 + this.max(this.height(node.left), this.height(node.right));
53
54        let balance = this.getBalance(node);
55
56        // LL Case
57        if (balance > 1 && key < node.left.key) return this.rightRotate(node);
58
59        // RR Case
60        if (balance < -1 && key > node.right.key) return this.leftRotate(node);
61
62        // LR Case
63        if (balance > 1 && key > node.left.key) {
64            node.left = this.leftRotate(node.left);
65            return this.rightRotate(node);
66        }
67
68        // RL Case
69        if (balance < -1 && key < node.right.key) {
70            node.right = this.rightRotate(node.right);
71            return this.leftRotate(node);
72        }
73
74        return node;
75    }
76}

Related Lessons

AVL Tree

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Convert Sorted List to Binary Search Tree

Balance a Binary Search Tree

AI resume checker — match your resume to the job description

Stack

Queue

Deque

Circular Queue

Frequently Asked Questions

What is an AVL Tree?

What is a Balance Factor?

AVL vs BST?