Insert Into a Binary Search Tree
WHAT IT SAYS
Insert a new value into a BST so that the tree remains a valid BST.
WHAT IT'S REALLY ASKING
"Search for the value you want to insert. The search will fail — the value isn't there — but look at WHERE it fails: at a null pointer that is the one and only place a search for this value would ever look. Hang the node on that null, and every future search finds it. Insertion is not a separate operation; it is a search that ends by writing."
Find some legal spot and restructure around it
Anywhere from O(h) to O(n), plus a correctness argument you now oweTreat insertion as tree surgery: pick a position — maybe the root, maybe somewhere convenient — and rearrange pointers or rotate nodes until the ordering invariant holds again everywhere.
WHERE THE WORK IS WASTED — Restructuring answers a question nobody asked. The BST invariant is a system of constraints, and inserting at an arbitrary spot violates some of them, which you then repair — but there exists a position where inserting violates NOTHING, and the ordinary search algorithm walks straight to it. Every rotation, every re-hung subtree, every re-checked invariant is the cost of ignoring that the data structure's own lookup procedure doubles as its placement procedure.
The failed search dead-ends exactly where the value belongs.
Run the standard BST search for the new value v: at each node, go left if v is smaller, right if larger. Since v is absent, the walk eventually steps into a null. Two claims about that null, and together they are the whole algorithm. Claim one: placing v there keeps the tree valid. Every comparison along the path was a constraint v already satisfies — each left turn certified v smaller than that ancestor, each right turn certified it larger. The null slot's permitted range (the interval carved out by all those ancestors) contains v by construction, because v itself steered the walk. Nothing anywhere else in the tree even relates to this slot's constraints. Claim two: it is the UNIQUE such leaf position. Any future search for v will make identical comparisons and take the identical path — determinism of the walk means this null is precisely where every lookup for v will arrive. Insert anywhere else (even somewhere technically legal after restructuring) and you've done extra work to reach the same searchable state this position gives for free. The insight generalises past this problem: in a search structure, the failure point of a lookup is the insertion point. Hash tables (the empty bucket the probe lands on), skip lists, tries — the same principle everywhere. A search structure that tells you 'not found' is simultaneously telling you 'and here is where it would go'. One honest caveat that motivates half of computer science: repeated insertion of sorted input walks the same rightward path every time, producing a spine — h degrades to n. The insertion is still correct; it is the BALANCE that suffers, which is exactly the problem AVL and red-black trees exist to solve with their rotations. Rotations are the fix for degradation, not a component of insertion.
Walk to the null, write the node
O(h) time — one root-to-leaf path — O(1) iterative space, O(h) recursiveIteratively: descend comparing v to each node, remembering the parent, until you step into null; attach the new node to the parent on the side you fell off. Recursively: insert(node, v) returns the (possibly new) subtree root — null returns a fresh node, otherwise recurse into the correct child and reassign the pointer. The reassignment idiom handles the empty-tree case with zero special-casing.
Failure Point Is the Insertion Point
YOU'LL SEE IT AGAIN WHEN
- The structure supports deterministic lookup, so a failed search terminates at a unique, reproducible location.
- Every constraint the new element must satisfy was already verified by the comparisons that steered the search toward that location.
- You feel the urge to restructure after inserting — the sign you inserted somewhere a search would never have gone.