Binary Search Trees

The BST invariant

A Binary Search Tree is a binary tree with one extra rule imposed on every node, not just its immediate children:

For any node n, every value in n's left subtree is strictly less than n.val, and every value in n's right subtree is strictly greater than n.val.

That "every value in the subtree," not "just the direct children," is the entire subtlety of this topic — it's what separates a real BST from a tree that merely "looks sorted" one level at a time. (LeetCode's constraints usually assume unique values; if duplicates are allowed, you must pick and consistently apply a convention — e.g., duplicates go right — or the invariant becomes ambiguous.)

This single rule is what turns a tree into a search structure: at any node, comparing your target to node.val tells you which entire subtree to discard, the same way binary search discards half an array each step (see the Binary Search topic — a BST is structurally the same divide-and-conquer idea, just materialized as pointers instead of index arithmetic).

Search and insert

Both operations follow identical logic: compare, then recurse (or loop) into exactly one subtree.

Notice the return root pattern in insert: at every level of the recursion, the (possibly-unchanged) subtree root gets reattached to its parent. This is the standard idiom for "modify a tree and return the new root" — you'll see it again in delete below, and it generalizes to the "compute something, then reconnect" recursive shape used throughout the Advanced Tree Patterns subtopic.

Delete — the operation everyone gets wrong on the first try

Deletion has three cases, and only the third one is genuinely tricky:

1. Leaf node — just remove it (return None to the parent).
2. One child — splice it out by returning that one child up to the parent.
3. Two children — you cannot simply remove the node; you'd orphan one entire subtree. Instead, replace the node's value with its inorder successor (the smallest value in its right subtree, found by walking node.right all the way left) or equivalently its inorder predecessor (the largest value in its left subtree), then recursively delete that successor/predecessor from its original position — which is now guaranteed to be a case-1-or-2 deletion, since the successor by construction has no left child.

The reason the successor is safe to promote: it's the smallest value greater than everything in the left subtree, and by definition of "smallest," it has no left child of its own — so deleting it from its original spot is always a trivial case-1/case-2 deletion, never another two-child case.

Why balance matters

Every BST operation above runs in O(h), where h is the tree's height — not O(log n). Those are only the same thing when the tree is balanced (height ≈ log n). Insert values in sorted order with no rebalancing, and you get a tree that's really a linked list in disguise: every node has only a right child, h = n, and search/insert/delete all silently degrade to O(n). This is precisely the recursion-tree intuition from the Big-O & Complexity Analysis topic — a "1 recursive call, shrink by a constant" shape is O(n), not O(log n).

This is also why interviewers care whether you say "O(h)" instead of reflexively saying "O(log n)" — stating the balanced-case bound as if it were guaranteed is a tell that you're pattern-matching rather than reasoning. Self-balancing variants (AVL trees, red-black trees) exist specifically to guarantee h = O(log n) by rebalancing on every insert/delete, but they're out of scope for coding interviews — knowing why they exist is the expected depth.

Structure	Search	Insert	Delete	Notes
Unsorted array	O(n)	O(1) amortized (append)	O(n)	No ordering to exploit
Sorted array	O(log n)	O(n) (shifting)	O(n) (shifting)	Fast search, slow mutation
BST (balanced)	O(log n)	O(log n)	O(log n)	Fast search and mutation
BST (degenerate/skewed)	O(n)	O(n)	O(n)	Effectively a linked list
Hash Map/Set	O(1) avg	O(1) avg	O(1) avg	No ordering preserved — can't do range queries or "kth smallest"

Validating a BST — the bug almost everyone writes first

The instinctive first attempt checks only the immediate parent-child relationship:

This passes simple cases but fails on a tree like 5 -> (3, 8) where 8's left child is 6: 6 < 8 satisfies the local check, but 6 is in 5's right subtree, where every value must be > 5 — 6 passes that too, so this particular example needs one more level (8's left child being 4, which is < 5) to actually break it. The point stands generally: local checks only compare a node to its direct children, never to the full chain of ancestors that bounds where it's allowed to sit.

The fix is to thread a valid (low, high) range down through the recursion, tightening it as you descend:

Every node is now checked against the tightest bounds implied by every ancestor on the path from the root, not just its immediate parent — which is exactly the guarantee the BST invariant makes.

Inorder traversal gives sorted order

Because inorder visits left → root → right, and the BST invariant guarantees left-subtree-values < root < right-subtree-values at every level, an inorder traversal of a BST always produces values in strictly increasing order. This single fact is the workhorse of BST problems: "kth smallest," "closest value," "two-sum on a BST," and validation itself can all be reframed as "run inorder traversal and reason about the resulting sorted sequence" (checking it's strictly increasing is an equally valid way to validate a BST).

Complexity summary

Operation	Balanced BST	Skewed BST	Space
Search / Insert / Delete	O(log n)	O(n)	O(h) recursion stack
Inorder traversal (full)	O(n)	O(n)	O(h)

Common pitfalls

• Checking only immediate children instead of a valid range — covered above, but worth repeating: this is the single most common bug in this entire subtopic.
• Strict vs. non-strict inequalities. Decide up front whether duplicates are allowed and where they go (typically the right subtree), and apply that consistently in search/insert/delete/validate — mixing < and <= across your own functions is a common self-inflicted bug.
• Forgetting to reconnect after delete/insert. Both operations must return the (possibly new) subtree root so the caller can reattach it — forgetting the root.left = insert(root.left, val) assignment silently drops the mutation.
• Assuming a BST is height-balanced. It isn't, by definition — balance is a separate, optional property. Don't reason about complexity as if h = log n unless the problem guarantees a balanced tree.
• Using integer overflow-prone sentinels. float("-inf")/float("inf") work cleanly in Python; in languages with fixed-width integers, be careful that your sentinel bounds can't collide with legal node values at the extremes of the input range.