Binary Search Tree

Binary Search Tree

Imagine you keep your books on a shelf, but with one rule: for any book you place, every book to its left comes earlier in the alphabet and every book to its right comes later. To find a title you never scan the whole shelf — you glance at the middle book, decide "earlier" or "later", and throw away half the shelf. Repeat. That is the whole idea of a Binary Search Tree (BST): it takes the halving power of binary search on a sorted array and makes it work on a structure you can also insert into and delete from cheaply, without shifting everything over.

A plain sorted array gives fast lookup but slow insertion (you shove elements aside). A linked list gives fast insertion but slow lookup (you walk node by node). A BST is the negotiated middle: it keeps data ordered while letting each operation follow a single root-to-leaf path.

Precise definition

A BST is a binary tree — every node has at most two children, a left and a right — obeying the BST ordering invariant: for every node x,

• every key in x's left subtree is less than x.key, and
• every key in x's right subtree is greater than x.key.

The word every is the trap most people miss: the rule is not just about immediate children, it applies to the entire subtree. A node can locally look fine yet globally violate the invariant. One clean consequence: an in-order traversal (left, node, right) visits keys in strictly ascending sorted order. That single property is how you verify, sort, and reason about a BST.

Worked example: searching for 35, then inserting it

Take the tree above (before the red node). Its keys are 50, 30, 70, 20, 40, 80. We search for 35, comparing at each step:

• At root 50: 35 < 50 → go left. (compare #1)
• At 30: 35 > 30 → go right. (compare #2)
• At 40: 35 < 40 → go left. (compare #3)
• Left child of 40 is empty → 35 not found, after just 3 comparisons on a 6-node tree.

To insert 35 we follow the exact same path and place it where the search fell off the tree — as the left child of 40 (the red node). Insertion is "search, then attach at the null spot." Both operations cost O(h), where h is the height. Here h = 3, so ≤ 3 comparisons — versus scanning all 6 keys in an unsorted list.

Deletion has three cases. Deleting a leaf (e.g. 20): just detach it. Deleting a node with one child (e.g. 40 after adding 35): splice the child up in its place. Deleting a node with two children (e.g. 30): replace its key with its in-order successor — the smallest key in its right subtree — then delete that successor (which has at most one child). This preserves the sorted invariant.

Complexity — and the honest worst case

Every core operation (search, insert, delete, min, max, successor) walks one root-to-leaf path, so each is O(h). The catch is that h depends entirely on shape:

• Best / average case: a reasonably balanced tree has height h ≈ log₂n, giving O(log n) operations. Inserting random keys yields expected height ≈2.99·log₂n (≈4.31·ln n), with the average search path even shorter at ≈1.39·log₂n (≈2·ln n) — logarithmic on average either way.
• Worst case: insert already-sorted keys (10, 20, 30, 40, …) and every node hangs off the right. The tree degenerates into a linked list with h = n, so operations become O(n). This is the killer weakness of the plain BST.

Because sorted or nearly-sorted input is common in practice, the plain BST's guarantee is fragile. That fragility is exactly why self-balancing variants exist.

Pitfalls and what an interviewer probes

• "Validate a BST" — the classic trap. Checking only left < node < right at each node is wrong: a deep descendant can violate the global rule. Correct approaches: carry a (min, max) range down the recursion, or do an in-order traversal and check it is strictly increasing.
• Duplicates. The clean definition uses strict inequalities and no duplicates. If you must allow them, decide a consistent convention (e.g. equal keys go right, or store a count) — and say so out loud.
• Confusing BST with binary heap. A heap only guarantees parent-vs-child ordering and gives no sorted traversal or O(log n) search by key; a BST orders left-vs-right across whole subtrees. Different tools.
• Forgetting the two-children delete case, or forgetting to re-link the parent pointer after splicing — a very common source of bugs.
• Not raising balance. Strong candidates volunteer that a plain BST degrades to O(n) and name the fix before being asked.

When it matters in practice + trade-offs

You almost never ship a raw BST — you ship a self-balancing one: Red-Black trees (Java's TreeMap/TreeSet, C++ std::map, Linux kernel schedulers) and AVL trees (stricter balance, faster lookups, more rotations on write). Databases and filesystems use the disk-friendly cousin, the B-tree. All keep h = O(log n) guaranteed, dodging the degenerate case.

Trade-offs against neighbouring structures:

• vs. hash table: a hash map gives O(1) average lookup but no order. Choose a balanced BST when you need ordered operations hashing can't do cheaply: range queries ("all keys in [x, y]"), successor/predecessor, min/max, or sorted iteration. That ordering is the BST's reason to exist.
• vs. sorted array: array lookup is O(log n) too and is more cache-friendly, but insert/delete is O(n) due to shifting. BST insert/delete is O(log n) when balanced — pick the tree when the data changes often.

Key takeaways

• A BST keeps data ordered so every core operation follows one root-to-leaf path costing O(h); in-order traversal yields sorted keys.
• Balanced → O(log n); but sorted-input insertion degenerates it to a list at O(n) — the reason real code uses Red-Black/AVL/B-trees.
• Validate with a propagated (min, max) range or an in-order check — never just local child comparisons.
• Prefer a balanced BST over a hash table when you need ordering: range queries, successor/predecessor, min/max, or sorted traversal.