AVL Tree Rotations Explained

Learn AVL Tree Rotations Explained with practical examples, explanations, best practices, and real-world coding techniques.

What Are AVL Tree Rotations?

AVL tree rotations are restructuring operations used to restore the balance of an AVL tree after an insertion or deletion changes its height. An AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of every node must remain within a specific range.

When a node becomes unbalanced, the tree can be rearranged using one or two rotations. These rotations change the structure of the tree while preserving the binary search tree ordering of its elements.

Why Are Rotations Necessary?

Consider inserting values into a binary search tree in sorted order. The tree can gradually become skewed, making it behave more like a linked list. Searching, inserting, or deleting values can then approach O(n) time.

AVL trees prevent this problem by maintaining a balance factor for each node. When an insertion or deletion causes the balance factor to fall outside the allowed range, rotations are performed to restore the tree's height balance.

Balance Factor Meaning
-1 Left and right subtree heights differ by one
0 Left and right subtree heights are equal
1 Left and right subtree heights differ by one

A node becomes unbalanced when its balance factor becomes less than -1 or greater than 1.

The Four AVL Rotation Cases

AVL imbalance is commonly classified into four cases based on the direction of the imbalance and the location of the newly inserted node:

  • LL (Left-Left) case
  • RR (Right-Right) case
  • LR (Left-Right) case
  • RL (Right-Left) case
Case Imbalance Solution
LL Left subtree of left child Right rotation
RR Right subtree of right child Left rotation
LR Right subtree of left child Left rotation + right rotation
RL Left subtree of right child Right rotation + left rotation

LL Case: Right Rotation

The LL case occurs when a node becomes unbalanced because a value was inserted into the left subtree of its left child.

For example, inserting 30, 20, and 10 produces a left-heavy structure: 

    30
   /
  20
 /
10

A right rotation around 30 produces: 

    20
   /  \
 10    30

The right rotation moves the left child upward and moves the original root downward to the right.

Right Rotation Structure

        y                 x
       / \               / \
      x   T3    →       T1  y
     / \                   / \
    T1  T2                 T2  T3

RR Case: Left Rotation

The RR case occurs when a node becomes unbalanced because a value was inserted into the right subtree of its right child.

For example, inserting 10, 20, and 30 creates a right-heavy tree: 

10
  \
   20
     \
      30

A left rotation around 10 restores the balance: 

    20
   /  \
 10    30

Left Rotation Structure

    x                     y
   / \                   / \
  T1  y       →         x   T3
     / \               / \
    T2  T3             T1  T2

LR Case: Left Rotation Followed by Right Rotation

The LR case occurs when the new value is inserted into the right subtree of the left child. This creates a zig-zag structure, so a single rotation is not enough.

For example, inserting 30, 10, and 20 produces: 

    30
   /
 10
   \
    20

The first step is a left rotation on 10: 

    30
   /
  20
 /
10

The second step is a right rotation on 30: 

    20
   /  \
 10    30

Therefore, an LR imbalance requires two rotations: first left, then right.

RL Case: Right Rotation Followed by Left Rotation

The RL case is the opposite of the LR case. It occurs when a value is inserted into the left subtree of the right child.

For example, inserting 10, 30, and 20 produces: 

10
  \
   30
   /
  20

First, perform a right rotation on 30: 

10
  \
   20
     \
      30

Then perform a left rotation on 10: 

    20
   /  \
 10    30

Therefore, an RL imbalance requires two rotations: first right, then left.

How to Identify the Correct Rotation

The easiest way to identify an AVL rotation is to follow the path from the unbalanced node toward the inserted value.

  1. If the path is Left → Left, use a right rotation.
  2. If the path is Right → Right, use a left rotation.
  3. If the path is Left → Right, use a left rotation followed by a right rotation.
  4. If the path is Right → Left, use a right rotation followed by a left rotation.
Path Case Rotation
Left → Left LL Right
Right → Right RR Left
Left → Right LR Left + Right
Right → Left RL Right + Left

AVL Rotation Implementation in JavaScript

A rotation only changes a small number of references. The important part is preserving the subtree that moves between the nodes. 

function rightRotate(y) {
  const x = y.left;
  const subtree = x.right;

  x.right = y;
  y.left = subtree;

  return x;
}

function leftRotate(x) {
  const y = x.right;
  const subtree = y.left;

  y.left = x;
  x.right = subtree;

  return y;
}

The subtree variable is important because it prevents an existing part of the tree from being lost during the rotation.

Handling All Four Cases

During AVL insertion, the balance factor and the direction of the inserted value determine which rotation is required. 

if (balance > 1 && value < node.left.value) {
  // LL case
  return rightRotate(node);
}

if (balance < -1 && value > node.right.value) {
  // RR case
  return leftRotate(node);
}

if (balance > 1 && value > node.left.value) {
  // LR case
  node.left = leftRotate(node.left);
  return rightRotate(node);
}

if (balance < -1 && value < node.right.value) {
  // RL case
  node.right = rightRotate(node.right);
  return leftRotate(node);
}

Rotations Preserve BST Ordering

A rotation changes the shape of the tree without changing the sorted order of its values. This is one of the most important properties of AVL rotations.

For example, before and after an LL rotation, an inorder traversal still produces the same sorted sequence: 

Before:
    30
   /
  20
 /
10

Inorder:
10, 20, 30

After:
    20
   /  \
 10    30

Inorder:
10, 20, 30

The values remain in the same relative order; only their structural relationships change.

Rotation Complexity

AVL rotations involve a constant number of pointer or reference changes. Therefore, an individual rotation takes constant time.

Operation Time Complexity
Left rotation O(1)
Right rotation O(1)
LR rotation O(1)
RL rotation O(1)

Although a single rotation is O(1), finding and repairing imbalances during insertion or deletion takes O(log n) in an AVL tree because the tree remains balanced.

Common Mistakes with AVL Rotations

  • Using a right rotation for an RR case instead of a left rotation.
  • Using a left rotation for an LL case instead of a right rotation.
  • Forgetting that LR and RL cases require two rotations.
  • Overwriting a subtree reference before moving it to the correct position.
  • Failing to update node heights after a rotation.
  • Returning the wrong node as the new root of the rotated subtree.
  • Checking only the height difference without considering the direction of the imbalance.

AVL Rotation Quick Reference

Case Pattern First Rotation Second Rotation
LL Left → Left Right None
RR Right → Right Left None
LR Left → Right Left Right
RL Right → Left Right Left

Key Takeaways

  • AVL rotations restore balance after structural changes.
  • LL imbalance is fixed with a right rotation.
  • RR imbalance is fixed with a left rotation.
  • LR imbalance requires a left rotation followed by a right rotation.
  • RL imbalance requires a right rotation followed by a left rotation.
  • Individual AVL rotations take O(1) time.
  • Rotations preserve the binary search tree ordering of the elements.
  • Correct height updates are essential when implementing AVL trees.

Code Examples 

function rightRotate(y) {
  const x = y.left;
  const subtree = x.right;

  x.right = y;
  y.left = subtree;

  return x;
}

function leftRotate(x) {
  const y = x.right;
  const subtree = y.left;

  y.left = x;
  x.right = subtree;

  return y;
}
    
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function rightRotate(y) {
  const x = y.left;
  const subtree = x.right;

  x.right = y;
  y.left = subtree;

  return x;
}

const root = new Node(30);
root.left = new Node(20);
root.left.left = new Node(10);

const balancedRoot = rightRotate(root);

console.log(balancedRoot.value);
console.log(balancedRoot.left.value);
console.log(balancedRoot.right.value);
    
function rightRotate(y) {
  const x = y.left;
  const subtree = x.right;

  x.right = y;
  y.left = subtree;

  return x;
}

function leftRotate(x) {
  const y = x.right;
  const subtree = y.left;

  y.left = x;
  x.right = subtree;

  return y;
}

// LR structure:
//      30
//     /
//    10
//      \
//       20

let root = {
  value: 30,
  left: {
    value: 10,
    left: null,
    right: {
      value: 20,
      left: null,
      right: null
    }
  },
  right: null
};

root.left = leftRotate(root.left);
root = rightRotate(root);

console.log(root.value);
console.log(root.left.value);
console.log(root.right.value);

Pro Tip

When identifying an AVL imbalance, trace the path from the unbalanced node toward the inserted value. Left-Left means right rotation, Right-Right means left rotation, Left-Right means left then right, and Right-Left means right then left.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.