DSA An AVL Tree from Scratch

The problem: the structure spec

The spec asks for a binary search tree built from scratch that keeps itself balanced. It supports one operation, insert, plus two checks the article runs after every script: the inorder walk reads sorted, and every node's balance factor stays within one of zero.

Each node stores its height in edges, where an empty child counts as height minus one and a lone node has height zero. The balance factor of a node is its left height minus its right height. An insert returns through its ancestors, updating heights and rotating wherever the balance breaks.

script = [
    ("left-left", [30, 20, 10], 20, 1),
    ("right-right", [10, 20, 30], 20, 1),
    ("left-right", [30, 10, 20], 20, 1),
    ("right-left", [10, 30, 20], 20, 1),
    ("sorted fifteen", list(range(1, 16)), 8, 3),
    ("reverse fifteen", list(range(15, 0, -1)), 8, 3),
]
for name, values, root, h in script:
    print(name, "| inserts:", len(values), "| expected root:", root, "| expected height:", h)

The four three-insert rows are the four rotation cases. The two fifteen-insert rows stress the design with the worst input order a plain search tree can receive. Expected roots and heights come from the spec's balance rule, not from any library.

Intuition: the naive design, a plain search tree

The naive design is a plain binary search tree. Insert walks down to the right leaf position and attaches the new node there. Nothing is stored besides the value and the two children, and nothing is ever repaired.

The design works until the input arrives sorted. Sorted inserts always turn right, and the tree degenerates into a chain. Every later operation then walks the whole chain, and the structure is a list wearing a tree's clothes.

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

def plain_insert(root, value, compared):
    if root is None:
        return Node(value)
    compared[0] += 1
    if value < root.value:
        root.left = plain_insert(root.left, value, compared)
    else:
        root.right = plain_insert(root.right, value, compared)
    return root

def edges_height(node):
    if node is None:
        return -1
    return 1 + max(edges_height(node.left), edges_height(node.right))

compared = [0]
root = None
for v in range(1, 16):
    root = plain_insert(root, v, compared)
print("root:", root.value)
print("height in edges:", edges_height(root))
print("insert comparisons for 15 sorted values:", compared[0])

Fifteen sorted values produce height 14 and 105 comparisons. The tree holds the right values in the right order and is still a failure as a structure. Height is the defect the real design exists to control.

Brute force: the naive design's bill, counted

Run as the article's brute-force baseline, the plain tree pays one comparison per level on every insert. Sorted input maximises every path, so its insert bill is the triangular count of the input size.

Rebuilding the tree from scratch after every insert would restore balance by force. That repair costs a full rebuild per insert and throws away the structure each time. The counted chain below is the honest naive bill, and it already argues for repair on the way back up instead.

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

def plain_insert(root, value, compared):
    if root is None:
        return Node(value)
    compared[0] += 1
    if value < root.value:
        root.left = plain_insert(root.left, value, compared)
    else:
        root.right = plain_insert(root.right, value, compared)
    return root

def edges_height(node):
    if node is None:
        return -1
    return 1 + max(edges_height(node.left), edges_height(node.right))

for n in [7, 15, 31]:
    compared = [0]
    root = None
    for v in range(1, n + 1):
        root = plain_insert(root, v, compared)
    print("sorted inserts:", n, "- height:", edges_height(root),
          " comparisons:", compared[0])

The comparison count is exactly the triangular number at each size. Doubling the input roughly quadruples the bill. A structure whose worst common input behaves this way needs balancing as a built-in rule, not as an occasional cleanup.

The optimal solution: stored heights, balance factors, rotations

The real design stores a height on every node, and every insert repairs the path it took on the way back up: update the height, read the balance factor, and rotate when it leaves the range from minus one to one. That repair loop is the whole design.

A rotation swaps a node with one child while preserving inorder order. The left-right and right-left cases first straighten the child with one rotation, then rotate the node itself. Rotations update the lower node's height before the new root's height, because the root's height depends on it.

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 0

def height(node):
    return node.height if node is not None else -1

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

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

def rotate_right(y):
    x = y.left
    middle = x.right
    x.right = y
    y.left = middle
    update(y)
    update(x)
    return x

def rotate_left(x):
    y = x.right
    middle = y.left
    y.left = x
    x.right = middle
    update(x)
    update(y)
    return y

def insert(node, value):
    if node is None:
        return AVLNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    update(node)
    if balance(node) > 1:
        if balance(node.left) < 0:
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance(node) < -1:
        if balance(node.right) > 0:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

def build(values):
    root = None
    for v in values:
        root = insert(root, v)
    return root

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)

def balanced(node):
    if node is None:
        return True
    return (abs(balance(node)) <= 1 and balanced(node.left)
            and balanced(node.right))

cases = [
    ("left-left", [30, 20, 10]),
    ("right-right", [10, 20, 30]),
    ("left-right", [30, 10, 20]),
    ("right-left", [10, 30, 20]),
    ("sorted fifteen", list(range(1, 16))),
    ("reverse fifteen", list(range(15, 0, -1))),
]
for name, values in cases:
    root = build(values)
    out = []
    inorder(root, out)
    ok = out == sorted(values) and balanced(root)
    print(name, "| root:", root.value, "| height:", root.height,
          "| inorder sorted:", out == sorted(values),
          "| balanced:", balanced(root), "| PASS" if ok else "| FAIL")

Every script row passes both checks. Sorted fifteen finishes at root 8 with height 3, against the plain tree's height 14 on the same input. The inorder walk is untouched by every rotation, which the sorted check proves row by row.

Walkthrough: inserting 10, 20, 30 step by step

The script inserts three values in rising order. After each insert the walk prints the root, its stored height, its balance factor, and the inorder list. The third insert is where the design must act.

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 0

def height(node):
    return node.height if node is not None else -1

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

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

def rotate_right(y):
    x = y.left
    middle = x.right
    x.right = y
    y.left = middle
    update(y)
    update(x)
    return x

def rotate_left(x):
    y = x.right
    middle = y.left
    y.left = x
    x.right = middle
    update(x)
    update(y)
    return y

def insert(node, value):
    if node is None:
        return AVLNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    update(node)
    if balance(node) > 1:
        if balance(node.left) < 0:
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance(node) < -1:
        if balance(node.right) > 0:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

def build(values):
    root = None
    for v in values:
        root = insert(root, v)
    return root

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)

def balanced(node):
    if node is None:
        return True
    return (abs(balance(node)) <= 1 and balanced(node.left)
            and balanced(node.right))

root = None
for v in [10, 20, 30]:
    root = insert(root, v)
    out = []
    inorder(root, out)
    print("inserted", v, "| root:", root.value, "| root height:", root.height,
          "| root balance:", balance(root), "| inorder:", out)
print("children of root:", root.left.value, "and", root.right.value)

The first two inserts lean right without breaking the rule. The third pushes the root's balance factor to minus two during the return climb. A single left rotation at the root then promotes 20, and the printed state shows the repaired tree.

Complexity

Balanced height stays within a constant factor of log n, so insert walks O(log n) levels and does constant repair work per level, giving O(log n) time per insert. The tree stores one node per value, so space is O(n), with O(log n) recursion on the insert path.

The printed heights are the evidence. A plain tree's height on sorted input equals its node count minus one. This design's height follows the logarithm instead.

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 0

def height(node):
    return node.height if node is not None else -1

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

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

def rotate_right(y):
    x = y.left
    middle = x.right
    x.right = y
    y.left = middle
    update(y)
    update(x)
    return x

def rotate_left(x):
    y = x.right
    middle = y.left
    y.left = x
    x.right = middle
    update(x)
    update(y)
    return y

def insert(node, value):
    if node is None:
        return AVLNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    update(node)
    if balance(node) > 1:
        if balance(node.left) < 0:
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance(node) < -1:
        if balance(node.right) > 0:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

def build(values):
    root = None
    for v in values:
        root = insert(root, v)
    return root

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)

def balanced(node):
    if node is None:
        return True
    return (abs(balance(node)) <= 1 and balanced(node.left)
            and balanced(node.right))

def plain_height(n):
    return n - 1

for n in [15, 31, 63, 127]:
    root = build(list(range(1, n + 1)))
    print("sorted inserts:", n, "- plain height:", plain_height(n),
          " avl height:", root.height, " root:", root.value)

At 127 sorted inserts the plain tree stands 126 edges tall. The balanced tree stands 6. Every insert and every search inherits that gap, because path length is height.

Edge cases and pitfalls

An empty tree has height minus one by this article's convention, and its inorder walk is empty. The first insert creates a lone node of height zero. Both ends of the convention show in the run below.

A duplicate value goes to the right subtree in this design, matching the plain insert rule. The tree then holds both copies, and the inorder walk stays non-decreasing. Updating heights in the wrong order inside a rotation is the classic implementation bug: the new root must be updated after the lowered node, or every stored height above it rots.

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 0

def height(node):
    return node.height if node is not None else -1

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

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

def rotate_right(y):
    x = y.left
    middle = x.right
    x.right = y
    y.left = middle
    update(y)
    update(x)
    return x

def rotate_left(x):
    y = x.right
    middle = y.left
    y.left = x
    x.right = middle
    update(x)
    update(y)
    return y

def insert(node, value):
    if node is None:
        return AVLNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    update(node)
    if balance(node) > 1:
        if balance(node.left) < 0:
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance(node) < -1:
        if balance(node.right) > 0:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

def build(values):
    root = None
    for v in values:
        root = insert(root, v)
    return root

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)

def balanced(node):
    if node is None:
        return True
    return (abs(balance(node)) <= 1 and balanced(node.left)
            and balanced(node.right))

print("empty height:", height(None))
root = build([42])
out = []
inorder(root, out)
print("single node:", out, "height:", root.height, "balanced:", balanced(root))
root = build([5, 5])
out = []
inorder(root, out)
print("duplicate insert:", out, "balanced:", balanced(root), "root height:", root.height)
root = build([30, 10, 20])
print("left-right root:", root.value,
      "children:", root.left.value, root.right.value,
      "balanced:", balanced(root))

The left-right case ends with root 20 and children 10 and 30, exactly the straightened shape the double rotation promises. Duplicates and empty inputs behave by rule rather than by accident. The design's contract is the script from the first section, and every row of it passes.