Insertion & Deletion

March 2026 · 22 min read

We know the four rotation cases. Now let's use them inside the full AVL insert and delete algorithms. The pattern is always the same: do the normal BST operation, walk back up the tree updating heights, and rotate whenever a node's balance factor hits ±2.

AVL Insertion

The Algorithm

1. BST insert: Walk down the tree like a normal BST insertion. Place the new node as a leaf.
2. Walk back up: As the recursion unwinds, update each ancestor's height.
3. Check balance: At each ancestor, compute the balance factor. If it's ±2, apply the appropriate rotation.
4. Stop after first fix: For insertion, at most one rotation (single or double) is needed to restore balance. Once fixed, all ancestors above are also balanced.

Complete Insert Code

TreeNode* insert(TreeNode* node, int key) {
    // 1. Normal BST insert
    if (!node) return new TreeNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;  // duplicate, no insert

    // 2. Update height
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. Get balance factor
    int bf = balance(node);

    // 4. Four rotation cases
    // LL: left-left, straight path
    if (bf > 1 && key < node->left->key)
        return rotateRight(node);

    // RR: right-right, straight path
    if (bf < -1 && key > node->right->key)
        return rotateLeft(node);

    // LR: left-right, zig-zag
    if (bf > 1 && key > node->left->key) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    // RL: right-left, zig-zag
    if (bf < -1 && key < node->right->key) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;  // balanced, no rotation needed
}

Walkthrough: Inserting 3, 2, 1

Animation: Build an AVL Tree

Watch how inserting [30, 20, 10, 25, 28, 27] builds a balanced AVL tree. Each rebalance shows which rotation fires.

AVL Deletion

Deletion follows the same pattern, but with two differences from insertion:

• BST delete first: Use the standard BST delete logic (no child, one child, or in-order successor replacement).
• Multiple rotations possible: Unlike insert (at most 1 rotation), deletion can require O(log n) rotations in the worst case, one at each level as we walk back up.

The Algorithm

1. BST delete: Find and remove the node using standard BST deletion.
2. Walk back up: Update heights and check balance factors at every ancestor.
3. Rotate as needed: Each unbalanced ancestor gets the appropriate rotation. Unlike insert, we don't stop after one fix; we check every ancestor.

Deciding Which Rotation for Delete

The four cases are the same, but the detection logic uses the child's balance factor rather than comparing the deleted key:

TreeNode* deleteNode(TreeNode* node, int key) {
    // 1. Standard BST delete
    if (!node) return nullptr;
    if (key < node->key)
        node->left = deleteNode(node->left, key);
    else if (key > node->key)
        node->right = deleteNode(node->right, key);
    else {
        // Found the node to delete
        if (!node->left || !node->right) {
            TreeNode* child = node->left ? node->left : node->right;
            if (!child) { delete node; return nullptr; }
            *node = *child; delete child;
        } else {
            // In-order successor (smallest in right subtree)
            TreeNode* succ = node->right;
            while (succ->left) succ = succ->left;
            node->key = succ->key;
            node->right = deleteNode(node->right, succ->key);
        }
    }

    // 2. Update height
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. Rebalance (same four cases)
    int bf = balance(node);

    if (bf > 1 && balance(node->left) >= 0)
        return rotateRight(node);
    if (bf > 1 && balance(node->left) < 0) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (bf < -1 && balance(node->right) <= 0)
        return rotateLeft(node);
    if (bf < -1 && balance(node->right) > 0) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

Insert vs Delete: Key Differences

Walkthrough: Deleting from an AVL Tree

Starting tree: {10, 5, 20, 3, 8, 15, 25, 2}. Delete node 15.

What's Next

We've covered the full AVL insert and delete algorithms. The final post analyzes AVL tree performance, compares it with red-black trees, and covers the patterns that come up in interviews.