Binary Search Tree

How it works, step by step

1. 1

   One rule, everywhere: keys smaller than a node live in its left subtree, bigger keys live in its right subtree.

2. 2

   Search: start at the root. Equal? Found. Smaller? Go left. Bigger? Go right. Repeat until you hit the key or fall off the tree.

3. 3

   Insert: run the same search. It always ends at an empty spot - and that empty spot is exactly where the new node belongs.

4. 4

   Delete: a leaf just disappears; a node with one child is replaced by that child; a node with two children first swaps its key with its in-order successor.

5. 5

   Every step drops a whole subtree, so a balanced tree answers in O(log n) comparisons - about 20 steps for a million keys.

6. 6

   Bonus: an in-order walk (left, node, right) visits the keys in sorted order - free sorted output, any time.

The code, in JavaScript

class Node {
  constructor(key) {
    this.key = key;
    this.left = null;    // everything smaller lives down here
    this.right = null;   // everything bigger lives down here
  }
}

function insert(root, key) {
  const node = new Node(key);
  if (root === null) return node;      // empty tree: new node is the root

  let cur = root;
  for (;;) {
    if (key < cur.key) {
      if (cur.left === null) { cur.left = node; break; }   // empty spot!
      cur = cur.left;
    } else {
      if (cur.right === null) { cur.right = node; break; } // (>= goes right)
      cur = cur.right;
    }
  }
  return root;             // the root never changes on a non-empty tree
}

let root = null;
for (const k of [8, 3, 10, 1, 6, 14, 4]) root = insert(root, k);
// Shape now:        8
//                 /   \
//                3     10
//               / \      \
//              1   6      14
//                 /
//                4

Dry run: insert 8, 3, 10, 1, 6, 14, 4 - then search for 6 and 7

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• The O(log n) promise requires balance, and a plain BST does nothing to keep it. Insert 1, 2, 3, 4, 5 in that order and you have built a linked list - search, insert and delete all become O(n). That failure mode is exactly why AVL trees, Red-Black trees and B-trees exist: the same rule, plus rotations that force the height to stay logarithmic.
• Equal keys need a policy: always right, always left, or a count field on the node. There is no default, and answering "it depends" without picking one fails interviews - while mixing policies in one tree silently loses data.
• Delete-with-two-children must go through the in-order successor (or predecessor). Grabbing one of the two children and linking it up directly either drops the other subtree or hangs keys where the order rule no longer holds. Copy the successor's key up, then delete the successor - it has at most one child by construction.
• Validating a BST needs min/max bounds passed down, not parent-child checks. The classic wrong validator compares each node only with its own children - and accepts a 6 hiding deep inside the right subtree of a 10, because every local pair looks fine. Carry (low, high) down and tighten one bound at every step.

Binary Search Tree vs. its closest relatives