Skip to content
My Docs

AVL Tree Rotations

Generated on 2025-07-10 02:04:06 Algorithm Cheatsheet for Technical Interviews

AVL Tree Rotations Cheatsheet

Section titled “AVL Tree Rotations Cheatsheet”

1. Quick Overview

Section titled “1. Quick Overview”

AVL trees are self-balancing Binary Search Trees (BSTs). Rotations are fundamental operations used to maintain the balance property: the height difference (balance factor) between the left and right subtrees of any node should not be more than 1. When insertions or deletions violate this balance, rotations are performed to re-balance the tree. There are four main rotation types: Left Rotation, Right Rotation, Left-Right Rotation, and Right-Left Rotation.

When to Use:

  • When you need a BST with guaranteed logarithmic time complexity for search, insertion, and deletion operations.
  • When the data changes frequently, and maintaining balance is critical for performance.

2. Time & Space Complexity

Section titled “2. Time & Space Complexity”
OperationTime ComplexitySpace Complexity
Single RotationO(1)O(1)
Double RotationO(1)O(1)

Note: Rotations are constant-time operations. However, the overall time complexity for insertion and deletion in an AVL tree remains O(log n) because you might need to traverse the tree to find the insertion/deletion point and then traverse back up to the root to check and perform rotations.

3. Implementation

Section titled “3. Implementation”

The following implementations assume a node structure with key, height, left, and right attributes.

Helper Functions (Python):

class Node:
    def __init__(self, key):
        self.key = key
        self.height = 1  # Height starts at 1 for a single node
        self.left = None
        self.right = None


def height(node):
    if node is None:
        return 0
    return node.height


def update_height(node):
    """Updates the height of the given node based on its children."""
    node.height = 1 + max(height(node.left), height(node.right))


def get_balance(node):
    if node is None:
        return 0
    return height(node.left) - height(node.right)

Helper Functions (Java):

class Node {
    int key;
    int height;
    Node left;
    Node right;


    Node(int key) {
        this.key = key;
        this.height = 1; // Height starts at 1 for a single node
        this.left = null;
        this.right = null;
    }
}


int height(Node node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}


void updateHeight(Node node) {
    node.height = 1 + Math.max(height(node.left), height(node.right));
}


int getBalance(Node node) {
    if (node == null) {
        return 0;
    }
    return height(node.left) - height(node.right);
}

Helper Functions (C++):

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


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


int height(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}


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


int getBalance(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

Rotations (Python):

def right_rotate(z):
    """Performs a right rotation on node z."""
    y = z.left
    T3 = y.right


    # Perform rotation
    y.right = z
    z.left = T3


    # Update heights
    update_height(z)
    update_height(y)


    return y  # New root


def left_rotate(z):
    """Performs a left rotation on node z."""
    y = z.right
    T2 = y.left


    # Perform rotation
    y.left = z
    z.right = T2


    # Update heights
    update_height(z)
    update_height(y)


    return y  # New root

Rotations (Java):

Node rightRotate(Node z) {
    Node y = z.left;
    Node T3 = y.right;


    // Perform rotation
    y.right = z;
    z.left = T3;


    // Update heights
    updateHeight(z);
    updateHeight(y);


    return y; // New root
}


Node leftRotate(Node z) {
    Node y = z.right;
    Node T2 = y.left;


    // Perform rotation
    y.left = z;
    z.right = T2;


    // Update heights
    updateHeight(z);
    updateHeight(y);


    return y; // New root
}

Rotations (C++):

Node* rightRotate(Node* z) {
    Node* y = z->left;
    Node* T3 = y->right;


    // Perform rotation
    y->right = z;
    z->left = T3;


    // Update heights
    updateHeight(z);
    updateHeight(y);


    return y; // New root
}


Node* leftRotate(Node* z) {
    Node* y = z->right;
    Node* T2 = y->left;


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


    // Update heights
    updateHeight(z);
    updateHeight(y);


    return y; // New root
}

Double Rotations (Python):

def left_right_rotate(z):
    """Performs a left rotation on z's left child, then right rotation on z."""
    z.left = left_rotate(z.left)
    return right_rotate(z)


def right_left_rotate(z):
    """Performs a right rotation on z's right child, then left rotation on z."""
    z.right = right_rotate(z.right)
    return left_rotate(z)

Double Rotations (Java):

Node leftRightRotate(Node z) {
    z.left = leftRotate(z.left);
    return rightRotate(z);
}


Node rightLeftRotate(Node z) {
    z.right = rightRotate(z.right);
    return leftRotate(z);
}

Double Rotations (C++):

Node* leftRightRotate(Node* z) {
    z->left = leftRotate(z->left);
    return rightRotate(z);
}


Node* rightLeftRotate(Node* z) {
    z->right = rightRotate(z->right);
    return leftRotate(z);
}

4. Common Patterns

Section titled “4. Common Patterns”
  • LL (Left-Left): Requires a single Right Rotation. Occurs when the balance factor is 2 and the left child’s balance factor is >=0.
  • RR (Right-Right): Requires a single Left Rotation. Occurs when the balance factor is -2 and the right child’s balance factor is <=0.
  • LR (Left-Right): Requires a Left Rotation on the left child, followed by a Right Rotation on the node. Occurs when the balance factor is 2 and the left child’s balance factor is < 0.
  • RL (Right-Left): Requires a Right Rotation on the right child, followed by a Left Rotation on the node. Occurs when the balance factor is -2 and the right child’s balance factor is > 0.

Example (LL):

Before rotation:

     z (bf=2)
    /
   y (bf=1)
  /
 x

After right rotation on z:

    y
   / \
  x   z

Example (LR):

Before rotation:

     z (bf=2)
    /
   y (bf=-1)
    \
     x

After rotations:

  1. Left rotate y:
     z (bf=2)
    /
   x
  / \
 y
  1. Right rotate z:
   x
  / \
 y   z

5. Pro Tips

Section titled “5. Pro Tips”
  • Height Updates: Always update the heights of the affected nodes after performing a rotation. Update the heights of the rotated nodes before updating the height of the new root.
  • Balance Factor Calculation: The balance factor is crucial for determining which rotation is needed. Double-check your calculation.
  • Root Update: After a rotation, remember to update the root of the tree if the rotation occurs at the root level.
  • Null Pointer Checks: Always handle null pointers when calculating heights or accessing children of nodes.
  • Order of Operations: When inserting or deleting, traverse up the tree from the inserted/deleted node to the root, checking the balance factor at each node and performing rotations as needed.

Common Mistakes to Avoid:

  • Forgetting to update the heights of the nodes after a rotation.
  • Incorrectly calculating the balance factor.
  • Not updating the root of the tree after a rotation that changes the root.
  • Incorrectly identifying the rotation case (LL, RR, LR, RL).
  • Not handling null pointers.

6. Practice Problems

Section titled “6. Practice Problems”

  1. LeetCode 1382. Balance a Binary Search Tree: Given a binary search tree, return a balanced binary search tree with the same node values. A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

  2. Implement AVL Tree Insertion: Implement the insertion operation for an AVL tree, including the necessary rotations to maintain balance. (This is a common interview question.)

7. Templates

Section titled “7. Templates”

These templates are designed to be easy to copy and paste into your code and quickly adapt to your specific problem. They include the basic node structure and the rotation functions.

C++ Template:

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


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


int height(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}


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


int getBalance(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return height(node->left) - height(node->right);
}


Node* rightRotate(Node* z) {
    Node* y = z->left;
    Node* T3 = y->right;


    y->right = z;
    z->left = T3;


    updateHeight(z);
    updateHeight(y);


    return y;
}


Node* leftRotate(Node* z) {
    Node* y = z->right;
    Node* T2 = y->left;


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


    updateHeight(z);
    updateHeight(y);


    return y;
}


Node* leftRightRotate(Node* z) {
    z->left = leftRotate(z->left);
    return rightRotate(z);
}


Node* rightLeftRotate(Node* z) {
    z->right = rightRotate(z->right);
    return leftRotate(z);
}


// Example Usage (Insertion):
Node* insert(Node* node, int key) {
    // Standard BST insertion
    if (node == nullptr) {
        return new Node(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 keys not allowed
    }


    updateHeight(node);


    int balance = getBalance(node);


    // LL case
    if (balance > 1 && key < node->left->key) {
        return rightRotate(node);
    }


    // RR case
    if (balance < -1 && key > node->right->key) {
        return leftRotate(node);
    }


    // LR case
    if (balance > 1 && key > node->left->key) {
        return leftRightRotate(node);
    }


    // RL case
    if (balance < -1 && key < node->right->key) {
        return rightLeftRotate(node);
    }


    return node;
}

Python Template:

class Node:
    def __init__(self, key):
        self.key = key
        self.height = 1
        self.left = None
        self.right = None


def height(node):
    if node is None:
        return 0
    return node.height


def update_height(node):
    if node:
        node.height = 1 + max(height(node.left), height(node.right))


def get_balance(node):
    if node is None:
        return 0
    return height(node.left) - height(node.right)


def right_rotate(z):
    y = z.left
    T3 = y.right


    y.right = z
    z.left = T3


    update_height(z)
    update_height(y)


    return y


def left_rotate(z):
    y = z.right
    T2 = y.left


    y.left = z
    z.right = T2


    update_height(z)
    update_height(y)


    return y


def left_right_rotate(z):
    z.left = left_rotate(z.left)
    return right_rotate(z)


def right_left_rotate(z):
    z.right = right_rotate(z.right)
    return left_rotate(z)


# Example Usage (Insertion):
def insert(node, key):
    # Standard BST insertion
    if node is None:
        return Node(key)


    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node  # Duplicate keys not allowed


    update_height(node)


    balance = get_balance(node)


    # LL case
    if balance > 1 and key < node.left.key:
        return right_rotate(node)


    # RR case
    if balance < -1 and key > node.right.key:
        return left_rotate(node)


    # LR case
    if balance > 1 and key > node.left.key:
        return left_right_rotate(node)


    # RL case
    if balance < -1 and key < node.right.key:
        return right_left_rotate(node)


    return node

Java Template:

class Node {
    int key;
    int height;
    Node left;
    Node right;


    Node(int key) {
        this.key = key;
        this.height = 1;
        this.left = null;
        this.right = null;
    }
}


int height(Node node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}


void updateHeight(Node node) {
    if (node != null){
        node.height = 1 + Math.max(height(node.left), height(node.right));
    }
}


int getBalance(Node node) {
    if (node == null) {
        return 0;
    }
    return height(node.left) - height(node.right);
}


Node rightRotate(Node z) {
    Node y = z.left;
    Node T3 = y.right;


    y.right = z;
    z.left = T3;


    updateHeight(z);
    updateHeight(y);


    return y;
}


Node leftRotate(Node z) {
    Node y = z.right;
    Node T2 = y.left;


    y.left = z;
    z.right = T2;


    updateHeight(z);
    updateHeight(y);


    return y;
}


Node leftRightRotate(Node z) {
    z.left = leftRotate(z.left);
    return rightRotate(z);
}


Node rightLeftRotate(Node z) {
    z.right = rightRotate(z.right);
    return leftRotate(z);
}




// Example Usage (Insertion):
Node insert(Node node, int key) {
        // Standard BST insertion
        if (node == null) {
            return new Node(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 keys not allowed
        }


        updateHeight(node);


        int balance = getBalance(node);


        // LL case
        if (balance > 1 && key < node.left.key) {
            return rightRotate(node);
        }


        // RR case
        if (balance < -1 && key > node.right.key) {
            return leftRotate(node);
        }


        // LR case
        if (balance > 1 && key > node.left.key) {
            return leftRightRotate(node);
        }


        // RL case
        if (balance < -1 && key < node.right.key) {
            return rightLeftRotate(node);
        }


        return node;
    }

This cheatsheet provides a comprehensive overview of AVL tree rotations, including the necessary code and explanations to quickly understand and implement them. Remember to practice applying these rotations in various scenarios to solidify your understanding. Good luck!