DSA AVL Trees

An AVL tree is a self-balancing binary search tree that keeps every node's left and right subtree heights within one of each other, guaranteeing O(log n) operations even in the worst case.

Why Self-Balancing Trees?

A plain binary search tree only stays fast if it stays balanced. Insert already-sorted data and it degenerates into a straight chain of nodes, turning O(log n) search into O(n). Named after inventors Adelson-Velsky and Landis, the AVL tree fixes this by enforcing a balance condition after every insertion or deletion: for every node, the height of its left subtree and the height of its right subtree may differ by at most 1.

That difference - left height minus right height - is called the balance factor, and it must always be -1, 0, or 1. Whenever an insertion or deletion pushes a node's balance factor outside that range, the tree performs a rotation: a local restructuring of a few nodes that restores balance without disturbing the BST ordering invariant. Because each rotation is O(1) and at most O(log n) of them are needed per operation, an AVL tree keeps search, insert, and delete at O(log n) even in the worst case.

Balance Factor and the Four Rotation Cases

Example: Balance Factor and a Single Rotation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1   # height of a leaf is 1


def height(node):
    return node.height if node else 0


def balance_factor(node):
    return height(node.left) - height(node.right)


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


def rotate_right(y):
    x = y.left
    t2 = x.right

    x.right = y
    y.left = t2

    update_height(y)
    update_height(x)
    return x                  # x is the new subtree root


def rotate_left(x):
    y = x.right
    t2 = y.left

    y.left = x
    x.right = t2

    update_height(x)
    update_height(y)
    return y                  # y is the new subtree root


# Manually build a left-left heavy case: 30 with left child 20,
# which itself has left child 10.
root = Node(30)
root.left = Node(20)
root.left.left = Node(10)
update_height(root.left)
update_height(root)

print(balance_factor(root))    # 2 - unbalanced
root = rotate_right(root)      # fix it with a single right rotation
print(root.value, root.left.value, root.right.value)   # 20 10 30
print(balance_factor(root))    # 0 - balanced again

Inserting Into an AVL Tree

Insertion starts exactly like a normal BST insert: walk down comparing values until you find the right spot for the new node. The difference is what happens on the way back up the recursion - at each ancestor, recompute its height, compute its balance factor, and if it's out of range, apply one of four rotation patterns (left-left, right-right, left-right, or right-left) based on which side is heavy and which side of that side is heavy.

Example: Full AVL Insert With Rotations

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


def height(node):
    return node.height if node else 0


def balance_factor(node):
    return height(node.left) - height(node.right)


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


def rotate_right(y):
    x = y.left
    t2 = x.right
    x.right = y
    y.left = t2
    update_height(y)
    update_height(x)
    return x


def rotate_left(x):
    y = x.right
    t2 = y.left
    y.left = x
    x.right = t2
    update_height(x)
    update_height(y)
    return y


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    else:
        return node               # no duplicates

    update_height(node)
    balance = balance_factor(node)

    if balance > 1 and value < node.left.value:        # Left-Left
        return rotate_right(node)
    if balance < -1 and value > node.right.value:       # Right-Right
        return rotate_left(node)
    if balance > 1 and value > node.left.value:         # Left-Right
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1 and value < node.right.value:       # Right-Left
        node.right = rotate_right(node.right)
        return rotate_left(node)

    return node


def inorder(node, result=None):
    if result is None:
        result = []
    if node is None:
        return result
    inorder(node.left, result)
    result.append(node.value)
    inorder(node.right, result)
    return result


root = None
for value in [10, 20, 30, 40, 50, 25]:
    root = insert(root, value)

print(inorder(root))     # [10, 20, 25, 30, 40, 50] - still sorted
print(root.value)        # 30 - the tree re-balanced around a new root
print(height(root))      # 3 - not 6, even though 6 values were inserted

Example: AVL Stays Balanced on Sorted Input

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


def height(node):
    return node.height if node else 0


def balance_factor(node):
    return height(node.left) - height(node.right)


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


def rotate_right(y):
    x = y.left
    t2 = x.right
    x.right = y
    y.left = t2
    update_height(y)
    update_height(x)
    return x


def rotate_left(x):
    y = x.right
    t2 = y.left
    y.left = x
    x.right = t2
    update_height(x)
    update_height(y)
    return y


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    else:
        return node

    update_height(node)
    balance = balance_factor(node)

    if balance > 1 and value < node.left.value:
        return rotate_right(node)
    if balance < -1 and value > node.right.value:
        return rotate_left(node)
    if balance > 1 and value > node.left.value:
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1 and value < node.right.value:
        node.right = rotate_right(node.right)
        return rotate_left(node)

    return node


# Insert already-sorted data: 1, 2, 3, ..., 15
root = None
for value in range(1, 16):
    root = insert(root, value)

print(height(root))          # 4 - stays logarithmic (log2(15) is about 3.9)
print(balance_factor(root))  # always within -1, 0, or 1

# A plain (non-balancing) BST inserting the same sorted data would instead
# form a single 15-node chain with a height of 15, making every search O(n).
  • Balance factor equals height(left subtree) minus height(right subtree), and must stay in -1, 0, or 1
  • A single rotation fixes a left-left or right-right heavy case
  • A double rotation fixes a left-right or right-left heavy case
  • Tree height stays O(log n) no matter what order values are inserted in
  • Search, insert, and delete are all guaranteed O(log n), even in the worst case
Imbalance CaseFix
Left-Left (left child's left subtree too tall)Single right rotation
Right-Right (right child's right subtree too tall)Single left rotation
Left-Right (left child's right subtree too tall)Left rotation on the left child, then a right rotation on the node
Right-Left (right child's left subtree too tall)Right rotation on the right child, then a left rotation on the node
Note: AVL trees trade a little extra bookkeeping on every insert or delete for a hard guarantee on lookup speed - a solid default whenever reads vastly outnumber writes and worst-case latency matters.

Exercise: DSA AVL Trees

What defining property must every node in an AVL tree satisfy?

Keep Going

Data Structures Interview QuestionsPractice real questions asked for Data StructuresSoftware Engineer SalarySee what Software Engineer roles pay in the marketAuto Apply for JobsApply to open roles related to Data Structures and tweak your resume