The BST invariant
State the ordering rule over whole subtrees, validate it with a range rather than a parent check, and price search at height 20 against height a million.
A binary search tree holds one rule: every key in a node's left subtree is less than the node, and every key in its right subtree is greater. Not the left child and the right child — the entire subtrees. That distinction is the difference between a correct validator and the one almost everyone writes first.
Everything a BST is good at falls out of that rule. Search discards half the remaining keys per comparison because the rule is transitive, and an inorder walk comes out sorted because the rule holds at every level at once.
The bug the rule is written to prevent
This tree passes every parent-child check and is not a BST:
10
/ \
5 15
/ \
6 20
Look only at neighbours and all is well: 5 < 10, 15 > 10, 6 < 15, 20 > 15. But 6 sits inside 10's right subtree while being smaller than 10, so a search for 6 starts at 10, goes left because 6 is less than 10, and never reaches the right subtree where 6 actually sits. The tree is a lie about where its keys are.
A validator that compares each node with its children accepts this tree. The fix is to carry the range a node is allowed to be in, narrowing it on the way down:
def is_bst(node, low=float('-inf'), high=float('inf')):
if node is None:
return True
if not (low < node.val < high):
return False
return (is_bst(node.left, low, node.val) # left: capped by this node
and is_bst(node.right, node.val, high)) # right: floored by it
Going left replaces the upper bound with the current key; going right replaces the lower bound. When the recursion reaches 6 it is carrying low = 10, and 6 fails immediately. One pass, O(n) time, O(h) stack.
The second correct answer is an
inorder walk: a tree is a BST exactly
when its inorder sequence is strictly increasing, so keep the previous value and
compare. Both are O(n); the range version is easier to extend when the interviewer
asks about duplicates, because you decide which side gets <= in one place.
Search, insert, delete are all O(h)
def search(root, key):
node = root
while node:
if key == node.val:
return node
node = node.left if key < node.val else node.right
return None
def insert(node, key):
if node is None:
return Node(key)
if key < node.val:
node.left = insert(node.left, key)
elif key > node.val:
node.right = insert(node.right, key)
return node # equal key: no duplicate inserted
Insert always lands at a leaf. There is exactly one place a key can go without breaking the invariant, and following the comparisons finds it.
Delete is the only one with cases, and only because a node with two children cannot simply be removed:
def delete(node, key):
if node is None:
return None
if key < node.val:
node.left = delete(node.left, key)
elif key > node.val:
node.right = delete(node.right, key)
else:
if node.left is None: # 0 or 1 child: splice the child in
return node.right
if node.right is None:
return node.left
succ = node.right # 2 children: inorder successor
while succ.left:
succ = succ.left
node.val = succ.val # overwrite, then delete the successor
node.right = delete(node.right, succ.val)
return node
The successor is the leftmost node of the right subtree — the next key in sorted order, and the only key that can take this node's place without moving anything else. It has no left child by construction, so deleting it is the easy case.
h is log n only when the tree is balanced
Every cost above is O(h), and h is the number the interviewer is really asking about. A balanced tree of a million keys has h = 20, because 2²⁰ = 1,048,576. Each step is a pointer chase to a scattered heap address, roughly a main-memory reference at 100 ns, so a lookup costs about 20 × 100 ns = 2 µs.
Now insert 1, 2, 3, … 10⁶ in that order. Each key is larger than everything present, so it goes right every time and the tree is a chain of height 10⁶. The same lookup is now 10⁶ × 100 ns = 0.1 s. That is 50,000 times slower, and an in-memory data structure taking 100 ms per read is half a round trip from India to US East — the network would have been competitive.
Sorted input is not exotic. Timestamps, autoincrement ids and anything already ordered produce it, which is why production trees are balanced ones — AVL and red-black trees rotate on insert to hold h within a constant factor of log n. You will rarely be asked to implement rotations. You will often be asked what happens without them, and "it degenerates into a linked list on sorted input, so O(h) becomes O(n)" is the whole answer. Counting the height instead of the nodes is the same move as counting the innermost line in complexity by counting.
kth smallest is an inorder walk with a counter
Because inorder emits sorted keys, the kth smallest is the kth thing the walk produces. Use the explicit stack so you can stop:
def kth_smallest(root, k):
stack, node = [], root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
return None
Stopping early matters: this is O(h + k), so the 5th smallest of a balanced million-node tree touches about 25 nodes rather than 10⁶. Collecting the full walk into a list and indexing it is O(n) time and O(n) space for the same answer.
Lowest common ancestor, two ways
In a BST you never search. Walk down from the root: if both keys are smaller, the answer is left; if both are larger, it is right; the first node that sits between them — or equals one of them — is the ancestor, because that is where the two search paths diverge.
def lca_bst(root, a, b): # a and b are keys, not node references
node = root
while node:
if a < node.val and b < node.val:
node = node.left
elif a > node.val and b > node.val:
node = node.right
else:
return node # the split point
return None
Iterative, O(h), O(1) space, no recursion and nothing returned upward.
In a general binary tree there is no ordering to steer by, so you have to look everywhere, and the code becomes the postorder shape from structure and paths:
def lca(node, a, b): # the same two keys, matched by value
if node is None or node.val == a or node.val == b:
return node
l = lca(node.left, a, b)
r = lca(node.right, a, b)
if l and r: # a and b are on opposite sides: here
return node
return l or r # both below one side, or neither
That is O(n) — every node visited. On a million-node tree the BST version costs about 20 comparisons, roughly 2 µs, and the general version costs 10⁶ node visits, roughly 0.1 s. The invariant is worth 50,000×, and the only thing you did to earn it was maintain an ordering on insert.
Both functions take the same two arguments — keys, distinct, and both actually
present in the tree. That last clause is a precondition, not a detail, and
breaking it does not raise: it returns a confident wrong answer. Ask either one
for the ancestor of 5 and 99 in the three-node tree 10 with children 5 and 15.
lca_bst compares at the root, sees 5 on the left and 99 on the right, calls
that the split and returns 10. lca finds 5, finds nothing on the other side,
and returns the node holding 5. Both are wrong — 99 is not in the tree, so there
is no ancestor to name. State the precondition out loud, because the follow-up
is always "what if one of them is not in the tree": in the BST you answer it
with two O(h) searches, free next to the walk you were already doing; in the
general tree it costs a second O(n) pass, or a counter threaded through the
recursion so a candidate is returned only when both keys were seen.
In an interview
Say "for the whole subtree, not just the children" when you state the invariant, then write the range version. The interviewer is watching for exactly that sentence; the tree above is the standard counterexample they have ready.
Volunteer the height. "Search is O(h). h is log n if the tree is balanced and n if the keys arrived sorted, so with 10⁶ keys that is 20 steps or a million." That single line covers the follow-up they were going to ask, and it converts a complexity claim into a number.
The mistake that loses points: validating with node.left.val < node.val and
node.right.val > node.val. It is a local check for a global property, and the
counterexample is three levels deep.
Check yourself
Your validator compares each node with its two children and reports valid on the tree drawn above. Where does the range version reject it?
At the node 6. Descending right from 10 sets low = 10, and descending left from 15 only tightens the upper bound to 15, so 6 is checked against 10 < 6 < 15 and fails. The local check never sees the constraint from 10.
A BST holds 10⁶ keys inserted in increasing order. Estimate one lookup, and say what to change.
The tree is a chain of height 10⁶, so a lookup is 10⁶ pointer chases at about 100 ns each, roughly 0.1 s. Use a self-balancing tree — h returns to about 20, and the lookup to about 2 µs.
When does LCA by comparison stop being available, and what does that cost?
As soon as the tree is not a BST. Without an ordering you cannot prune, so you search both subtrees and return the node where the two finds meet: O(n) rather than O(h) — about 0.1 s against 2 µs on a balanced million-node tree.