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)
302010
A right rotation at 30 restores balance
201030
Unbalanced node (bf ±2)Pivot that becomes the new subtree rootNew subtree root after rotation

Algorithm Steps (Insertion)

  1. Insert the value the normal BST way (compare and recurse left/right)
  2. On the way back up the recursion, update each ancestor's height
  3. Compute the balance factor: height(left) − height(right)
  4. 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
  5. 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

Advertisement

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