Course contentsShow
← Computer Science
Lesson 539 of 2,87213. Balanced TreesFree lesson

AVL Insertion Algorithm

Insert a node using standard BST insertion, then rebalance from the insertion point upward.

What You'll Learn

You'll learn how to combine standard BST insertion with AVL rotations to keep a tree balanced after adding a new node.

The Complete AVL Insertion Process

Inserting into an AVL tree happens in two phases: first you insert like a normal BST, then you climb back up the tree fixing any imbalances you created.

Phase 1: Standard BST Insertion

Start by inserting the new node exactly as you would in a regular binary search tree—compare values and traverse left or right until you find an empty spot. Nothing special here yet.

Phase 2: Rebalance Upward

Here's where AVL magic happens. After placing the new node, backtrack from the insertion point toward the root, updating balance factors at each ancestor node.

At each node on the way up:

  1. Recalculate its balance factor (height of left subtree minus height of right subtree)
  2. Check if it's imbalanced (balance factor is -2 or +2)
  3. If imbalanced, identify the pattern and apply the appropriate rotation:
    • Left-heavy with left-heavy child? Single right rotation
    • Right-heavy with right-heavy child? Single left rotation
    • Left-heavy with right-heavy child? Left-right double rotation
    • Right-heavy with left-heavy child? Right-left double rotation
  4. Stop climbing once you've rotated (the tree above is now balanced)

Think of It Like Jenga

Inserting is like adding a block to a Jenga tower. You place it (BST insert), then check if the tower is still stable by examining each level from bottom to top. If you spot wobble, you stabilize that section with a rotation, and the whole structure stays upright.

Why Climb Upward?

The new node can only affect the heights of its ancestors—nodes below it or in other branches aren't impacted. Checking upward is efficient and sufficient.

Key Takeaway: AVL insertion = BST insert + bottom-up rebalancing using rotations to restore the height-balance invariant.