Binary Search Trees Explained — Insert, Search, Delete Visually

A binary search tree (BST) is what you get when you take the idea behind binary search — cut the problem in half with every comparison — and build a data structure around it. Instead of a sorted array you cannot cheaply insert into, you get a tree you can grow, shrink, and query, all in O(log n) time when things go well.

In this guide we will build a tree by hand, trace search and all three delete cases, see exactly how a BST degenerates into a glorified linked list, and understand why balanced variants like AVL trees exist. Everything here is easier to *watch* than to read, so keep the visualizer open alongside.

The one rule that makes everything work

A BST is a binary tree with a single invariant: at every node, all values in the left subtree are smaller than the node, and all values in the right subtree are larger. Not just the immediate children — the entire subtrees. That recursive guarantee is the whole trick.

Why does it matter? Because it turns every node into a signpost. Standing at a node holding 50 and looking for 64, you know — without inspecting a single node on the left — that 64 cannot possibly be over there. One comparison discards an entire subtree. If the tree is reasonably balanced, each level holds roughly half the remaining candidates, so every step down halves the search space, exactly like binary search on an array.

Insert, traced step by step

Insertion is a search that ends by attaching a new leaf where the search fell off the tree. Let us insert the sequence 50, 30, 70, 20, 40, 60, 80 into an empty tree:

1. 50 — tree is empty, so 50 becomes the root.
2. 30 — 30 < 50, go left; nothing there, attach 30 as the left child of 50.
3. 70 — 70 > 50, go right; attach 70 as the right child of 50.
4. 20 — 20 < 50 (left), 20 < 30 (left again); attach under 30.
5. 40 — 40 < 50 (left), 40 > 30 (right); attach as 30's right child.
6. 60 — 60 > 50 (right), 60 < 70 (left); attach under 70.
7. 80 — 80 > 50 (right), 80 > 70 (right); attach as 70's right child.

The result is a perfectly balanced tree: 50 at the root, 30 and 70 in the middle level, and 20, 40, 60, 80 as leaves. Seven nodes, three levels — and any value can be found in at most three comparisons. This insertion order was chosen deliberately; hold that thought, because a different order for the *same values* produces a very different tree.

insert(node, value):
  if node is null:
    return new Node(value)   // fell off the tree — attach here
  if value < node.value:
    node.left = insert(node.left, value)
  else:
    node.right = insert(node.right, value)
  return node

Search is just binary search on a tree

Searching for 60 in the tree above: 60 > 50, go right. 60 < 70, go left. Found it — two comparisons for a seven-node tree. The procedure is identical to binary search on a sorted array; the difference is that the "midpoints" are baked into the structure as nodes rather than computed from indices. Miss cases are just as cheap: searching for 65 walks 50 → 70 → 60, finds no right child under 60, and reports failure in three comparisons instead of scanning all seven values.

Delete: the three cases

Deletion is where BSTs earn their reputation for being fiddly. The problem: removing a node leaves a hole, and the repair must preserve the invariant. There are exactly three situations.

• Case 1 — leaf. No children, no problem: unlink it. Deleting 20 above just removes the node.
• Case 2 — one child. Splice the node out and let its only child take its place. The child's whole subtree was already on the correct side of everything above, so the invariant survives untouched.
• Case 3 — two children. You cannot just remove the node — both subtrees need a parent. Instead, *replace its value* with its inorder successor (the smallest value in the right subtree), then delete that successor node from the right subtree.

Trace case 3 by deleting the root, 50. Its inorder successor is the leftmost node of the right subtree: from 70, walk left to 60. Copy 60 into the root, so the tree now reads 60 at the top — still bigger than everything on the left (which is untouched) and smaller than everything remaining on the right, because 60 was the *minimum* over there. Then delete the old 60, which is a leaf: case 1. Every two-child deletion bottoms out in one of the easy cases, because the successor never has a left child — if it did, that child would be smaller, contradicting "leftmost".

The degeneration problem

Now insert the same seven values in sorted order: 20, 30, 40, 50, 60, 70, 80. Every new value is larger than everything before it, so every insertion goes right, right, right. The "tree" is a straight chain — structurally a linked list wearing a tree costume. Searching for 80 now takes seven comparisons, not three. Height is n instead of log n, and every operation collapses from O(log n) to O(n).

Why balanced trees exist

A plain BST's performance is hostage to insertion order. Self-balancing trees fix this by detecting lopsidedness and repairing it with rotations — local restructurings that lift a subtree up one level and push its parent down, without ever breaking the ordering invariant. An AVL tree tracks the height of each subtree and rotates whenever the two sides of any node differ in height by more than one. The payoff: the height is *guaranteed* to stay O(log n), no matter how adversarial the insertion order is.

The cost of the guarantee is a little bookkeeping on every insert and delete. For most workloads that trade is obviously worth it, which is why the trees inside real libraries are essentially never plain BSTs.

Inorder traversal: sorted order for free

Visit the left subtree, then the node, then the right subtree — recursively. On our example tree that yields 20, 30, 40, 50, 60, 70, 80: the values come out sorted, always, directly from the invariant. This is the property that makes BSTs more than a fast lookup table. Range queries ("every key between 35 and 65"), finding the k-th smallest element, iterating a map in key order — all fall out of inorder traversal in a way hash tables simply cannot offer.

inorder(node):
  if node is null: return
  inorder(node.left)
  visit(node.value)     // values arrive in sorted order
  inorder(node.right)

Where BSTs show up in practice

• Ordered maps and sets — C++ std::map/std::set and Java's TreeMap/TreeSet are balanced BSTs (red-black trees, a cousin of AVL). You reach for them precisely when you need sorted iteration or range queries.
• Database indexes — the B-trees behind nearly every relational index are the same idea generalized: many keys per node to match disk and cache line sizes, but still "ordered keys, prune by comparison".
• Priority and interval structures — augmented BSTs power interval trees, order statistics, and scheduling structures where "smallest above x" must be fast.

Try it yourself

BST intuition is built with your hands, not your eyes. Insert a shuffled sequence and watch the tree stay bushy; insert a sorted one and watch it degenerate; delete a two-child node and watch the inorder successor climb into place. Then do the same inserts in the AVL visualizer and watch rotations refuse to let the tree go lopsided.