Binary Search Tree

Balancing (AVL)

What is an AVL Tree?

A plain BST offers no guarantee about its shape: insert values in the wrong order and it degenerates into a linked list with O(n) operations (see BST Insertion). An AVL tree fixes this by adding one rule on top of the normal BST ordering: for every node, the heights of its left and right subtrees may differ by at most 1. This is called the balance factor, and it's recalculated bottom-up after every insertion or deletion.

How Do Rotations Work?

Whenever an insertion pushes a node's balance factor to +2 or -2, the tree is out of balance and needs a rotation, a local rearrangement of a few pointers that restores the height rule without breaking the BST ordering. There are four possible imbalance shapes, and each has a matching fix: a single rotation for the two "straight-line" cases (Left-Left, Right-Right), and a double rotation for the two "zig-zag" cases (Left-Right, Right-Left).

Left-Left

A left-heavy node whose left child is also left-heavy. Fixed with a single right rotation.

Right-Right

A right-heavy node whose right child is also right-heavy. Fixed with a single left rotation.

Left-Right

A left-heavy node whose left child is right-heavy (zig-zag). Fixed by rotating the left child left, then the node right.

Right-Left

A right-heavy node whose right child is left-heavy (zig-zag). Fixed by rotating the right child right, then the node left.

Inserting 10 unbalances 30 (Left-Left)

A right rotation at 30 restores balance

Unbalanced node (bf ±2)Pivot that becomes the new subtree rootNew subtree root after rotation

Algorithm Steps (Insertion)

Insert the value the normal BST way (compare and recurse left/right)
On the way back up the recursion, update each ancestor's height
Compute the balance factor: height(left) − height(right)
If the balance factor is +2 or -2, identify which of the 4 cases applies and rotate:
- Left-Left → single right rotation
- Right-Right → single left rotation
- Left-Right → left rotation on the left child, then right rotation on the node
- Right-Left → right rotation on the right child, then left rotation on the node
Return the (possibly new) subtree root to the parent call

Time Complexity

Best/Average/Worst Case: Height is always O(log n) → O(log n).

Time Complexity Analysis

Space Complexity

Because at most O(log n) ancestors need their balance factor rechecked after an insertion, and each rotation touches only a constant number of pointers, a single insertion or deletion does at most one rotation (single or double) to restore balance, so the extra bookkeeping AVL trees do is cheap.

The payoff is that an AVL tree's height is always O(log n), no matter what order values are inserted in. Unlike a plain BST, it can never degrade into a skewed shape. This makes search, insertion, and deletion all worst-case O(log n), not just average-case.

Daily DSA Challenge by Scale Engineer

Insert a value and watch the tree rotate itself back into balance

Tree is empty

No tree yet, insert a value or generate a random tree

Internal nodeLeaf nodeRootJust rotatedBalance factor

Test Your Knowledge before moving forward!

AVL Balancing Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

AVL Tree Insertion Implementation

// AVL Tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

const height = (node) => (node ? node.height : 0);
const balanceFactor = (node) => (node ? height(node.left) - height(node.right) : 0);
const updateHeight = (node) => {
  node.height = 1 + Math.max(height(node.left), height(node.right));
};

function rotateRight(y) {
  const x = y.left;
  const T2 = x.right;
  x.right = y;
  y.left = T2;
  updateHeight(y);
  updateHeight(x);
  return x; // new subtree root
}

function rotateLeft(x) {
  const y = x.right;
  const T2 = y.left;
  y.left = x;
  x.right = T2;
  updateHeight(x);
  updateHeight(y);
  return y; // new subtree root
}

// Insert a value and rebalance the tree, returning the (possibly new) root
function insert(node, value) {
  if (node === null) return new TreeNode(value);

  if (value < node.value) node.left = insert(node.left, value);
  else if (value > node.value) node.right = insert(node.right, value);
  else return node; // no duplicates

  updateHeight(node);
  const bf = balanceFactor(node);

  // Left-Left
  if (bf > 1 && value < node.left.value) return rotateRight(node);
  // Right-Right
  if (bf < -1 && value > node.right.value) return rotateLeft(node);
  // Left-Right
  if (bf > 1 && value > node.left.value) {
    node.left = rotateLeft(node.left);
    return rotateRight(node);
  }
  // Right-Left
  if (bf < -1 && value < node.right.value) {
    node.right = rotateRight(node.right);
    return rotateLeft(node);
  }

  return node;
}

// Usage example
let root = null;
[30, 20, 10, 25, 40, 50].forEach((value) => {
  root = insert(root, value);
});

Done With the Learning

Mark AVL Tree Balancing as done and view it on your dashboard

Explore Other Tree Topics

BST Insertion

BST Deletion

BST Searching

Red-Black Tree

Binary Tree Types

Structure & Properties