Binary Search Trees: Insert, Search and AVL Balancing

One invariant, three operations

A binary search tree (BST) stores keys under a single invariant: for every node, everything in its left subtree is smaller and everything in its right subtree is larger. That invariant alone is enough to make search, insert and delete all follow the same pattern — compare the target key to the current node and recurse left or right — turning what would otherwise be a linear scan into a path down the tree.

search(node, key):
  if node is null: return not found
  if key == node.key: return node
  if key < node.key: return search(node.left, key)
  else:                return search(node.right, key)
insert: search until you fall off the tree, attach a new leaf there
delete: 0 or 1 child -> splice node out; 2 children -> replace with in-order successor

Complexity depends entirely on the tree's shape

All three operations cost O(h), where h is the tree's height. For a perfectly balanced tree of n keys, h = O(log n), so search, insert and delete are all logarithmic. But a BST built by inserting keys already in sorted order degenerates into a straight chain, with h = n − 1: the tree becomes, structurally, a linked list, and every operation is O(n). The BST invariant guarantees correctness; it does not guarantee balance.

In-order traversal recovers the sorted order for free

Visiting a BST in-order (left subtree, node, right subtree, recursively) always yields the keys in ascending sorted order, a direct consequence of the search invariant. This is one reason to use a BST instead of a hash table when you need range queries or sorted iteration: a hash table gives O(1) average lookup but no ordering, while a balanced BST gives O(log n) lookup and sorted output as a byproduct.

AVL trees: balancing by rotation

An AVL tree (Adelson-Velsky and Landis, 1962) restores the logarithmic guarantee by enforcing a balance invariant after every insert and delete: for every node, the heights of its left and right subtrees differ by at most 1. When an operation violates that invariant, the tree performs a rotation — a local restructuring of a few pointers that restores balance without breaking the search-tree property.

right rotation around node y (fixes left-left imbalance):
      y                x
     / \                / \
    x   C     ->      A   y
   / \                    / \
  A   B                  B   C
(a left rotation is the mirror image)

Because a rotation only rearranges a constant number of pointers and at most one imbalance needs fixing per level on the path back to the root, each insert or delete costs O(log n) for the search plus O(log n) worst case for rebalancing. AVL trees keep height within about 1.44 log2(n), a tighter bound than a red-black tree, which trades slightly looser balance for fewer rotations per update.

Why balance is worth the bookkeeping

The whole appeal of a BST over a plain sorted array is O(log n) insert and delete instead of O(n) shifting. That appeal evaporates the moment the tree is allowed to degenerate. Self-balancing variants — AVL, red-black, splay trees — all exist to make the O(log n) guarantee hold for every sequence of operations, not just favourable ones, at the cost of a balance factor per node and occasional rotation work.

Frequently asked questions

Try it live

Everything above runs in your browser — open Binary Search Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.