SimuVedaAlgorithms Lab Open in the lab

Trees / Advanced

AVL Tree Insert Visualizer

A BST that keeps itself balanced. After each insert, if one side becomes more than 1 level taller, rotate to fix it.

Start the AVL Tree Insert simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(log n)
Average timeO(log n)
Worst timeO(log n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Insert 10. The tree is empty, so it becomes the root.
  2. Insert 20: 20 > 10, go right.
  3. Place 20 as a new leaf.
  4. Insert 30: 30 > 10, go right.
  5. Insert 30: 30 > 20, go right.
  6. Place 30 as a new leaf.
  7. 10 has balance -2, so it is out of balance.
  8. Right-Right case: rotate left at 10. 20 moves up.
  9. Insert 40: 40 > 20, go right.
  10. Insert 40: 40 > 30, go right.
  11. Place 40 as a new leaf.
  12. Insert 50: 50 > 20, go right.
  13. Insert 50: 50 > 30, go right.
  14. Insert 50: 50 > 40, go right.
  15. Place 50 as a new leaf.
  16. 30 has balance -2, so it is out of balance.
  17. Right-Right case: rotate left at 30. 40 moves up.
  18. Insert 25: 25 > 20, go right.
  19. Insert 25: 25 < 40, go left.
  20. Insert 25: 25 < 30, go left.
  21. Place 25 as a new leaf.
  22. 20 has balance -2, so it is out of balance.
  23. Right-Left case: rotate right at 40, then left at 20. 30 moves up.
  24. Done. Every node has a balance of -1, 0 or 1.

Try it with your own input →

AVL tree insert in Java, Python, C++, C and JavaScript

Node insert(Node n, int v) {
  if (n == null) return new Node(v);
  if (v < n.val) n.left = insert(n.left, v);
  else if (v > n.val) n.right = insert(n.right, v);
  else return n;
  n.height = 1 + Math.max(h(n.left), h(n.right));
  int bal = h(n.left) - h(n.right);
  if (bal > 1 && v < n.left.val) return rotateRight(n);
  if (bal < -1 && v > n.right.val) return rotateLeft(n);
  if (bal > 1) { n.left = rotateLeft(n.left); return rotateRight(n); }
  if (bal < -1) { n.right = rotateRight(n.right); return rotateLeft(n); }
  return n;
}
def insert(n, v):
    if n is None:
        return Node(v)
    if v < n.val:
        n.left = insert(n.left, v)
    elif v > n.val:
        n.right = insert(n.right, v)
    else:
        return n
    n.height = 1 + max(h(n.left), h(n.right))
    bal = h(n.left) - h(n.right)
    if bal > 1 and v < n.left.val:
        return rotate_right(n)
    if bal < -1 and v > n.right.val:
        return rotate_left(n)
    if bal > 1:
        n.left = rotate_left(n.left)
        return rotate_right(n)
    if bal < -1:
        n.right = rotate_right(n.right)
        return rotate_left(n)
    return n
Node* insert(Node* n, int v) {
  if (!n) return new Node(v);
  if (v < n->val) n->left = insert(n->left, v);
  else if (v > n->val) n->right = insert(n->right, v);
  else return n;
  n->height = 1 + max(h(n->left), h(n->right));
  int bal = h(n->left) - h(n->right);
  if (bal > 1 && v < n->left->val) return rotateRight(n);
  if (bal < -1 && v > n->right->val) return rotateLeft(n);
  if (bal > 1) { n->left = rotateLeft(n->left); return rotateRight(n); }
  if (bal < -1) { n->right = rotateRight(n->right); return rotateLeft(n); }
  return n;
}
#define MAX2(x, y) ((x) > (y) ? (x) : (y))

struct Node* insert(struct Node* n, int v) {
  if (n == NULL) return newNode(v);
  if (v < n->val) n->left = insert(n->left, v);
  else if (v > n->val) n->right = insert(n->right, v);
  else return n;
  n->height = 1 + MAX2(h(n->left), h(n->right));
  int bal = h(n->left) - h(n->right);
  if (bal > 1 && v < n->left->val) return rotateRight(n);
  if (bal < -1 && v > n->right->val) return rotateLeft(n);
  if (bal > 1) { n->left = rotateLeft(n->left); return rotateRight(n); }
  if (bal < -1) { n->right = rotateRight(n->right); return rotateLeft(n); }
  return n;
}
function insert(n, v) {
  if (n === null) return { val: v, left: null, right: null, height: 1 };
  if (v < n.val) n.left = insert(n.left, v);
  else if (v > n.val) n.right = insert(n.right, v);
  else return n;
  n.height = 1 + Math.max(h(n.left), h(n.right));
  const bal = h(n.left) - h(n.right);
  if (bal > 1 && v < n.left.val) return rotateRight(n);
  if (bal < -1 && v > n.right.val) return rotateLeft(n);
  if (bal > 1) { n.left = rotateLeft(n.left); return rotateRight(n); }
  if (bal < -1) { n.right = rotateRight(n.right); return rotateLeft(n); }
  return n;
}

In an interview

Learn the four cases: LL and RR need one rotation, LR and RL need two. The small purple number by each node is its balance: left height − right height.

More trees