AVL tree insertion and rotations: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Maintain subtree heights and repair left-left, left-right, right-right and right-left imbalance with rotations. Duplicate keys are ignored.

After inserting a leaf, recompute heights toward the root. Rotate an imbalanced subtree once for an outside-heavy case, or twice for an inside-heavy case. Rotations preserve the BST ordering.

Open the 3D visualization

AVL tree insertion and rotations example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use AVL tree insertion and rotations

Ordered sets requiring logarithmic worst-case search and insertion.

Choosing an alternative

Ordinary BST insertion can produce a chain. Red-black trees control balance through colors rather than exact subtree heights.

Worked example: input and state changes

Example input

30,10,20,40,50,5 | 20

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Attach leaf 30; update heights toward the root.

    State at this checkpoint
    {
      "values": [
        30
      ],
      "active": [
        0
      ],
      "kind": "graph",
      "tree": true,
      "visited": [],
      "chosen": [],
      "heights": [
        1
      ]
    }
  2. Step 5: Key 30: height 3, balance 2.

    State at this checkpoint
    {
      "values": [
        30,
        10,
        null,
        null,
        20
      ],
      "active": [
        0
      ],
      "kind": "graph",
      "tree": true,
      "visited": [],
      "chosen": [],
      "heights": [
        3,
        2,
        0,
        0,
        1
      ]
    }
  3. Step 10: Key 20: height 3, balance -1.

    State at this checkpoint
    {
      "values": [
        20,
        10,
        30,
        null,
        null,
        null,
        40
      ],
      "active": [
        0
      ],
      "kind": "graph",
      "tree": true,
      "visited": [],
      "chosen": [],
      "heights": [
        3,
        1,
        2,
        0,
        0,
        0,
        1
      ]
    }
  4. Step 14: Left rotation at 30; promote 40.

    State at this checkpoint
    {
      "values": [
        20,
        10,
        40,
        null,
        null,
        30,
        50
      ],
      "active": [
        5,
        2
      ],
      "kind": "graph",
      "tree": true,
      "visited": [],
      "chosen": [],
      "heights": [
        3,
        1,
        2,
        0,
        0,
        1,
        1
      ]
    }
  5. Step 19: 20 found; AVL height 3.

    State at this checkpoint
    {
      "values": [
        20,
        10,
        40,
        5,
        null,
        30,
        50
      ],
      "active": [
        0
      ],
      "kind": "graph",
      "tree": true,
      "visited": [],
      "chosen": [],
      "heights": [
        3,
        2,
        2,
        1,
        0,
        1,
        1
      ],
      "result": 1,
      "ordered": [
        5,
        10,
        20,
        30,
        40,
        50
      ],
      "height": 3
    }

Expected final state

20 found; AVL height 3.

Complexity and input bounds

Family: Trees. Time complexity: O(log n) per insertion.

Implementation detail: This view implements insertion, all four rotation cases, and search; it does not implement AVL deletion. Inputs contain at most twelve keys. Downloads return membership and serialize inorder keys, tree height, heap-position keys and node heights for structural testing.

Space complexity: O(n) auxiliary storage for node records and serialized output; saved visualization frames use additional space.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

1..12 keys (0..99) | search key (0..99). Insert keys in order, then search.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Height of an empty subtree is zero. Update the demoted node before the promoted node after a rotation. Duplicate keys do not create extra nodes.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// AVL insertion/search, n 0..12 keys and target 0..99; duplicate keys ignored. Returns target membership. Output capacity at least 79: [0] unique count; [1..count] inorder keys; [16] root height; [17..47] 31 heap-position keys (-1 absent); [48..78] corresponding node heights (0 absent). Empty tree height 0. All four insertion rotation cases are implemented. O(log n) per operation, O(n log n) total insertion work, O(n) auxiliary space. This view does not implement AVL deletion. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(a, n, target, output) {
    let key = Array(256).fill(0); let left = Array(256).fill(0); let right = Array(256).fill(0); let parent = Array(256).fill(0); let height = Array(256).fill(0); let stack = Array(256).fill(0); let position = Array(256).fill(0);
    let root = 0; let count = 0; let u = 0; let p = 0; let value = 0; let balance = 0; let first = 0; let last = 0; let firstRight = 0; let lastRight = 0; let x = 0; let y = 0; let beta = 0; let direction = 0; let top = 0; let length = 0; let head = 0; let tail = 0; let found = 0;
    for (let i = 0; i < n; i++) {
        value = a[i]; u = root; p = 0;
        while (u != 0 && key[u] != value) { p = u; if (value < key[u]) { u = left[u]; } else { u = right[u]; } }
        if (u != 0) { continue; }
        u = ++count; key[u] = value; height[u] = 1; parent[u] = p;
        if (p == 0) { root = u; } else if (value < key[p]) { left[p] = u; } else { right[p] = u; }
        u = p;
        while (u != 0) {
            height[u] = height[left[u]]; if (height[right[u]] > height[u]) { height[u] = height[right[u]]; } height[u]++;
            balance = height[left[u]] - height[right[u]]; first = 0; last = 0; firstRight = 0; lastRight = 0;
            if (balance > 1) {
                last = u; lastRight = 1;
                if (height[left[left[u]]] < height[right[left[u]]]) { first = left[u]; firstRight = 0; }
            } else if (balance < -1) {
                last = u; lastRight = 0;
                if (height[right[right[u]]] < height[left[right[u]]]) { first = right[u]; firstRight = 1; }
            }
            if (last != 0) {
                for (let turn = 0; turn < 2; turn++) {
                    if (turn == 0 && first == 0) { continue; }
                    x = last; direction = lastRight; if (turn == 0) { x = first; direction = firstRight; }
                    y = right[x]; if (direction != 0) { y = left[x]; }
                    beta = left[y]; if (direction != 0) { beta = right[y]; }
                    p = parent[x];
                    if (direction != 0) { left[x] = beta; right[y] = x; } else { right[x] = beta; left[y] = x; }
                    parent[y] = p; parent[x] = y; if (beta != 0) { parent[beta] = x; }
                    if (p == 0) { root = y; } else if (left[p] == x) { left[p] = y; } else { right[p] = y; }
                    height[x] = height[left[x]]; if (height[right[x]] > height[x]) { height[x] = height[right[x]]; } height[x]++;
                    height[y] = height[left[y]]; if (height[right[y]] > height[y]) { height[y] = height[right[y]]; } height[y]++; u = y;
                }
            }
            u = parent[u];
        }
    }
    u = root;
    while (u != 0 && key[u] != target) { if (target < key[u]) { u = left[u]; } else { u = right[u]; } }
    if (u != 0) { found = 1; }
    for (let i = 0; i < 79; i++) { output[i] = 0; }
    for (let i = 0; i < 31; i++) { output[17 + i] = -1; }
    output[0] = count; output[16] = height[root]; u = root;
    while (u != 0 || top > 0) {
        while (u != 0) { stack[top++] = u; u = left[u]; }
        u = stack[--top]; output[++length] = key[u]; u = right[u];
    }
    if (root != 0) { stack[tail] = root; position[tail++] = 0; }
    while (head < tail) {
        u = stack[head]; p = position[head++]; output[17 + p] = key[u]; output[48 + p] = height[u];
        if (left[u] != 0) { stack[tail] = left[u]; position[tail++] = 2 * p + 1; }
        if (right[u] != 0) { stack[tail] = right[u]; position[tail++] = 2 * p + 2; }
    }
    return found;
}

Source

Original AVL research. The playground demonstrates insertion and all four balancing cases, not a complete container library or AVL deletion.