Listen, I've seen a lot of developers approach AVL trees thinking they are trying to build a perfectly symmetrical pyramid of nodes. If you've spent any time with basic binary search trees (BSTs), you know the nightmare of a "degenerate" tree—where you insert sorted data and end up with what is effectively a linked list, killing your $O(\log n)$ lookup time. The instinct is to think: "I just need to keep the tree perfectly even."

"But isn't a balanced tree just a perfectly symmetrical one?"

That's the biggest trap. If you try to force a tree to be perfectly symmetrical, you'll spend more time moving nodes around than actually searching for data. In an AVL tree, "balanced" doesn't mean "equal." It means the height difference between the left and right subtrees of any node is no more than one.

Imagine you have a tree with just two nodes: a root (10) and a left child (5). Is it symmetrical? No. Is it balanced? Yes. The left height is 1, the right height is 0. The difference is 1, which is perfectly legal. The moment you add a 2 as the left child of 5, the root (10) now has a left-height of 2 and a right-height of 0. That difference of 2 is where the AVL logic kicks in. We don't try to make it a perfect pyramid; we just rotate it enough to bring that difference back down to 1.

The Height-Balance Invariant and the Magic of Rotations

To make this work, every node needs to keep track of its own height. I usually recommend storing this as an integer in the node struct rather than calculating it on the fly—calculating height recursively during every insertion would turn your efficient $O(\log n)$ operation into an $O(n)$ slog.

When a node becomes unbalanced (balance factor > 1 or < -1), we perform rotations. Think of a rotation as "pulling" a node up to become the new parent and "pushing" the old parent down to become a child. There are four cases, but they really boil down to two types of moves: the Single Rotation and the Double Rotation.

struct Node {
    int key;
    Node *left, *right;
    int height;

    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

int getHeight(Node* n) {
    return n ? n->height : 0;
}

int getBalance(Node* n) {
    return n ? getHeight(n->left) - getHeight(n->right) : 0;
}

void updateHeight(Node* n) {
    if (n) {
        n->height = 1 + std::max(getHeight(n->left), getHeight(n->right));
    }
}

Handling the Four Rotation Scenarios

I like to think of rotations as fixing "lines" and "kinks." If the imbalance is a straight line (Left-Left or Right-Right), a single rotation fixes it. If it's a "kink" (Left-Right or Right-Left), you first rotate the child to turn the kink into a line, then rotate the parent to balance the whole thing. That's why it's called a Double Rotation.

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights (order matters!)
    updateHeight(y);
    updateHeight(x);

    return x; // New root
}

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    updateHeight(x);
    updateHeight(y);

    return y; // New root
}

When you implement your insert function, you do the standard BST insertion recursively. But the "secret sauce" is what happens as the recursion unwinds. On the way back up the call stack, you update the height of every ancestor and check the balance factor. If you find a balance factor of 2 (Left-heavy) and the new key was inserted into the left-child's left-subtree, you do one rotateRight. If it went into the left-child's right-subtree, you rotateLeft the child first, then rotateRight the current node.

📋 Practical Task

Implementing the AVL Tree Deletion Logic with Re-balancing

In the lesson, we focused on insertion. However, deleting a node from an AVL tree is significantly trickier because a single deletion can trigger a chain reaction of imbalances all the way up to the root.

Your Task: Complete the remove function for the AVL tree. Your implementation must:

• Perform a standard BST deletion (handling cases for leaf nodes, nodes with one child, and nodes with two children using the in-order successor).
• After the deletion, update the height of the current node.
• Check the balance factor and apply the necessary rotations (Single or Double) to restore the AVL invariant.
• Ensure that the function returns the new root of the subtree to the caller to maintain the tree structure.

Test your implementation by inserting the sequence {10, 20, 30, 40, 50, 25} and then deleting 10. Verify that the resulting tree remains balanced and the height of the root is no more than 3.