BST insert / delete / search

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A binary search tree keeps smaller values to the left and larger to the right, so finding a value is like the number-guessing game: compare, go left or right, repeat. The tree: 5 at the top; 3 and 6 below; 2 and 4 under 3; 7 under 6. Find 4: 4 < 5 go left, 4 > 3 go right, found. Three comparisons for six values, and the path only ever gets as long as the tree is tall.

Inserting is just a failed search: look for the value, and when you fall off the tree, hang the new node there. The hard case is deleting. Delete 3 by hand and you have a hole with two children, 2 and 4, dangling. Which one fills the hole? Both must stay on the correct sides of whatever goes there.

Build the structure, one piece at a time

Piece one: search. Start at the root. If the target equals the node, done. If smaller, go left; if larger, go right. If there is no child to go to, the value is absent.

Piece two: insert. Search; at the empty spot where the search ends, attach a new node. The new node is a leaf, so the only ordering it must respect is the path that led to it, and the path chose the correct side at every step.

Piece three: delete, in three cases. A leaf: unlink it. One child: replace the node by that child; the child's whole subtree was already on the correct side of everything above. Two children: find the inorder successor, the smallest value in the right subtree (go right once, then left as far as possible). Copy that value into the node, then delete the successor from the right subtree, which is easy because the smallest value there has no left child, so it is a leaf or a one-child case.

The sorted reading lost exactly one value, 3, and stayed sorted.

Why it is correct

The invariant: the BST rule holds after every operation. Search changes nothing. Insert adds a leaf at the position the comparisons chose, so every ancestor's rule is satisfied for the new node, and no other node's subtrees changed. For delete with two children, the successor s is the smallest value larger than the deleted value d, so:

every value in the left subtree < d < s ≤ every other value in the right subtree

Putting s where d was keeps the left subtree smaller and the right subtree larger. Removing s from the right subtree is a leaf or one-child deletion, already shown safe. The predecessor, the largest value on the left, works symmetrically.

Why it is fast

Each operation walks one path from the root downward, and the successor search continues along a path too, so the cost is the height h: O(h). For a balanced tree of a million values that is about 20 steps. For a tree that degenerated into a chain it is a million, which is why self-balancing trees exist; interview problems usually just ask for the O(h) version.

How to recognise it in an interview

"Insert into a BST", "delete a node from a BST", "search", "closest value to a target", "successor of a node". Say: "I will walk one path by comparison; for deletion with two children I replace the value with the inorder successor and delete that successor instead." Delete Node in a BST is the full three-case version. Insert into a Binary Search Tree is piece two. Closest Binary Search Tree Value is a search that remembers the nearest value seen on the way down, since the closest value is always on the search path or adjacent to it.

02The idea in one line

Walk left or right by comparison; delete replaces with the inorder successor.

Reach for it when: Insert, delete, search, closest value, successor/predecessor.

Cost: O(h) time.

03The walk-through, step by step

The video works one example: Delete 3 from [5,3,6,2,4,null,7]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Search for 3 starting at the root
2. 3 < 5: go left
3. Found 3, and it has two children: 2 and 4
4. Its inorder successor is the smallest key on the right: 4
5. Copy 4 into the node, so the order is preserved
6. Now delete the old 4, a leaf: simply unlink it
7. Gone. 2 < 4 < 5 still holds everywhere
8. Delete 2 (a leaf) would just unlink; delete 6 (one child) splices 7 up
9. Each operation follows one root-to-leaf path: O(h)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search Tree: BST range bounds, Inorder = sorted order, Build a balanced BST from sorted input.