Binary Search Tree

A binary search tree is a linked tree structure that keeps one strict promise at every node: everything in the left subtree is smaller, everything in the right subtree is larger. That single invariant lets insert, search, and delete all run in O(log n) time on average, because each comparison discards half the remaining tree.

You already know the strategy from the guessing game. "I'm thinking of a number." Higher. Lower. Higher. Each answer kills half the candidates, and twenty answers cover a million numbers. A binary search tree is that game frozen into pointers — every node is a question ("bigger or smaller than me?"), every edge one of the two answers.

How a Binary Search Tree Works

All three operations are the same walk wearing different hats: start at the root, compare, and let the answer pick the direction — smaller goes left, larger goes right, equal means you found it. They differ only in what happens when the walk ends.

insert(value) walks until the next step would land on an empty slot, then attaches a new node there. The new node is always a leaf — insertion never restructures anything above it. If the walk hits an equal value, this implementation skips the insert; duplicates are not stored. Into an empty tree, the new node becomes the root with no walk at all.

search(value) walks until it hits the value (found) or falls off the bottom into a null slot (not found). A miss is a certainty, not a shrug: the invariant guaranteed your value couldn't live anywhere you skipped.

delete(value) walks to the target, then splits into three cases by child count.

A leaf just gets unhooked — the parent's pointer becomes null and nothing else moves.

A node with one child gets spliced out: the parent's pointer swings past the doomed node and grabs the grandchild. The surviving subtree slides up one level intact — it already satisfied the ordering relative to the parent.

A node with two children is the case nobody gets right the first time. You cannot just remove it — both subtrees would be orphaned. Instead, find its in-order successor: step into the right subtree once, then walk left as far as possible. That leftmost node holds the smallest value larger than the target — the one value that can legally sit in the target's slot, still bigger than the whole left subtree, still smaller than the rest of the right. Copy the successor's value into the target, then remove the successor from the right subtree. The successor has no left child by construction, so removing it is always the easy leaf or one-child case: the hard case bottoms out in an easy one. (The in-order predecessor works symmetrically; this lesson animates the successor version, matching the displayed code.)

Binary Search Tree Step by Step

The player opens on an empty tree — BST initialized — empty. Build along with this trace using the Inputs panel: insert 50, 30, 70, 20, 40, 60, 80, in that order.

insert(50) finds no root, so 50 becomes the root without a single comparison. insert(30) plays one round of the game: 30 < 50, go left, the slot is null, attach 30 as the left child of 50. insert(70) mirrors it on the right. insert(20) needs two rounds — 20 < 50 go left, 20 < 30 go left, attach under 30. The remaining three each take two comparisons and land as 30's right child, 70's left child, and 70's right child. The result is a perfectly balanced tree: 50 on top, 30 and 70 below it, then 20, 40, 60, 80 along the bottom row.

Now search(40): at 50, 40 < 50, go left; at 30, 40 > 30, go right; at 40, equal — found at depth 2. Three comparisons against seven nodes, exactly the halving the guessing game promised.

Then the three deletes, one per case. delete(20) walks 50 → left, 30 → left, finds 20 with zero children, and unhooks it: 30's left pointer becomes null. delete(30) walks one step left from 50 and finds 30 now holding a single child, 40. The splice plays out in two beats: 50's left pointer swings to bypass 30 and point at 40, then 30 lifts away and 40 slides up into its slot.

delete(50) is the headline. The target is the root itself, matched on the first comparison, with two children — so the successor hunt begins. Step right to 70; 70 has a left child, so go left to 60; 60 has none, so 60 is the in-order successor. Its value is copied into the root's slot, and then 60 — a leaf — is spliced out of the right subtree. The final tree: 60 at the root, 40 on its left, 70 on its right with 80 hanging off 70's right side. Still a valid binary search tree at every node.

In the animation, the descending cursor lights each compared node while untouched subtrees stay at idle weight — the path is the operation. Inserts show a ghost slot at the attach point one beat before the node lands; deletes flag the doomed node, then either prune, splice (the parent's arrow visibly swinging to bypass), or run the successor walk — a dashed connector pairing successor with target — before the copy-and-splice.

Time and Space Complexity

The average-case time complexity is O(log n) because each comparison halves the candidates — but only while the tree stays roughly balanced, and nothing in a plain BST enforces balance. Insert 1, 2, 3, 4, 5 and every node attaches to the right of the previous one: the tree degenerates into a linked list, height becomes n, and every operation pays O(n). The guessing game stops being clever when every answer is "higher." Self-balancing variants — AVL trees, red-black trees, treaps — exist to prevent exactly this, which is why your standard library's TreeMap is a red-black tree rather than a vanilla BST.

One honesty note: the Max depth slider (3 to 5) is a layout knob for the canvas, not a BST property. A real binary search tree has no depth limit — degenerate chains grow freely. When an insert would exceed the slider's depth, the player says so explicitly rather than pretending the structure refused it; the Insert button likewise disables at the perfect-tree node count for the chosen depth.

Edge Cases

• Empty tree — search reports not found immediately; insert makes the new node the root; delete is a no-op.
• Delete the root — handled like any other node: a two-child root gets the successor treatment; a one-child root promotes its child to root.
• Insert a duplicate — the walk reaches the equal node and stops; nothing is inserted. Other conventions exist (a count field, or routing equals to the right), but mixing conventions inside one tree breaks search.
• Delete a missing value — the walk falls off the tree; not found, tree untouched.
• Single-node tree, delete it — the leaf case; the tree returns to empty.

Common Mistakes

• Treating the two-children delete as removable in place. It is not — both subtrees would be orphaned. You must promote the in-order successor (or predecessor) value into the slot first.
• Picking the wrong successor. The successor is the leftmost node of the right subtree — not any nearby leaf, never anything from the left subtree. Any other choice breaks the ordering invariant for some descendant.
• Inserting sorted data and wondering why everything is slow. Sorted input builds the degenerate chain. If you cannot randomize insertion order, you need a self-balancing tree.
• Confusing a BST with a heap. A BST orders left-to-right and supports ordered traversal and range queries; a heap orders parent-over-child and supports O(1) find-min but no ordered iteration.