Mastering Binary Search Trees (BST)
A Binary Search Tree (BST) is a binary tree with a powerful ordering property: for every node, all values in the left subtree are strictly less than the node's value, and all values in the right subtree are strictly greater. This single invariant enables O(log n) average-case search, insert, and delete — making BSTs the foundation for efficient dynamic sorted collections.
Think of a BST like a decision tree for looking up a word in a dictionary. At each page, you decide whether the word comes before or after, halving the remaining pages. A balanced BST with n nodes has height ≈ log₂(n), so searching among 1 million elements takes only ~20 comparisons. This principle — binary elimination — is the same idea behind binary search on sorted arrays, but BSTs also support efficient insertion and deletion, which sorted arrays do not.
BSTs appear in virtually every software system: database indexes (B-Trees), language standard libraries (C++ std::map, Java TreeMap), file system directories, auto-complete engines, and in-memory caches. They are also one of the most heavily tested topics in FAANG-level coding interviews, with problems spanning insertion, deletion, validation, traversal, and balancing.
How BSTs Work Internally
The BST Invariant
For every node N: all values in N.left are < N.value, and all values in N.right are > N.value. This must hold recursively for every subtree, not just the immediate children. A common interview mistake is checking only node.left < node < node.right instead of verifying the entire subtree. The correct approach passes min/max bounds down through recursion.
Search Path and Binary Elimination
Searching starts at the root and follows a single path downward. At each node, one comparison eliminates an entire subtree — roughly half the remaining nodes in a balanced tree. This gives O(log n) expected time, identical in spirit to binary search on a sorted array. The key difference: BSTs allow O(log n) insert and delete, while sorted arrays require O(n) shifts.
In-Order Traversal Produces Sorted Output
An in-order traversal (left → node → right) of a BST visits nodes in ascending sorted order. This is a defining property of BSTs and the basis for many interview solutions: checking if a tree is a valid BST, finding the kth smallest element, or converting a BST to a sorted linked list.
Balance and Degeneracy
A balanced BST has height O(log n), but inserting sorted data creates a degenerate tree — essentially a linked list with height O(n). This worst case destroys all performance guarantees. Self-balancing BSTs (AVL trees, Red-Black trees) use rotations to maintain O(log n) height after every insert/delete. In interviews, always mention this caveat when discussing BST complexity.
Predecessor and Successor
The in-order successor of a node is the smallest value greater than it (leftmost node in the right subtree, or the first ancestor where the node is in the left subtree). The predecessor is the largest value smaller than it. These concepts are essential for BST deletion (Case 3: two children) and for problems like "find next greater element" in a BST.
Memory Layout
BSTs share the same memory characteristics as general binary trees, but the ordering property impacts practical performance in important ways.
Node-Based Allocation
Each BST node stores a value plus two child pointers (left, right) and optionally a parent pointer. On a 64-bit system with 4-byte integers, each node costs ~28 bytes (4 data + 8×3 pointers). Nodes are heap-allocated and scattered in memory, meaning pointer chasing during traversal causes frequent cache misses — a significant constant-factor cost compared to array-based structures.
Height Determines Stack Usage
Recursive operations (search, insert, traversals) use O(h) stack space where h is the tree height. For a balanced tree, h = O(log n) which is small (~20 for 1M nodes). For a degenerate tree, h = O(n), which can cause stack overflow. Iterative versions eliminate this risk but are more complex to write, especially for delete.
Comparison with Hash Tables
Hash tables offer O(1) average lookup vs BST's O(log n), but BSTs maintain sorted order — enabling range queries, finding min/max, and in-order iteration. When you need both fast lookup AND sorted access, BSTs win. When you only need lookup by key, hash tables win. This tradeoff is a common system design interview question.
Core Operations Explained
BSTs support three fundamental operations (search, insert, delete) plus traversals and auxiliary queries (find min/max). The delete operation with its three cases is the most complex and most frequently tested in interviews.
Complexity Analysis
BST performance is directly tied to tree height h. For a balanced tree h = O(log n); for a degenerate tree h = O(n). Always state both average and worst case in interviews — omitting the worst case is a red flag to interviewers.
Operation Complexity
| Operation | Time |
|---|---|
| Search | O(log n) / O(n) |
| Insert | O(log n) / O(n) |
| Delete | O(log n) / O(n) |
| Find Min | O(log n) / O(n) |
| Find Max | O(log n) / O(n) |
| In-Order Traversal | O(n) |
| Build from N values | O(N log N) / O(N²) |
| Validate BST | O(n) |
Space Complexity
A BST with n nodes uses O(n) space for node storage. Recursive operations add O(h) stack space: O(log n) for balanced trees, O(n) for degenerate trees. The space advantage of BSTs over sorted arrays is that insert/delete do not require shifting elements — only pointer updates.
Critical Interview Patterns
BST problems are among the most frequently asked in technical interviews. They test your ability to exploit the ordering property, handle edge cases in deletion, and reason about tree balance. Master these patterns to handle the majority of BST interview questions.
Validate Binary Search Tree (LeetCode 98)
MediumDetermine if a binary tree satisfies the BST property. The most common mistake is only checking node.left < node < node.right — you must validate the ENTIRE subtree against inherited bounds.
Kth Smallest Element in BST (LeetCode 230)
MediumFind the kth smallest element in a BST. Exploits the fact that in-order traversal yields sorted order. Interviewers love this because it tests whether candidates understand the connection between BST structure and sorted output.
Delete Node in BST (LeetCode 450)
MediumImplement BST deletion with all three cases. This is the canonical BST problem — if you can't implement delete, interviewers will question your fundamental data structure knowledge.
Lowest Common Ancestor of BST (LeetCode 235)
MediumFind the lowest common ancestor (LCA) of two nodes in a BST. Unlike the general binary tree LCA problem, the BST property allows an elegant O(h) solution without visiting all nodes.
Convert Sorted Array to BST (LeetCode 108)
EasyBuild a height-balanced BST from a sorted array. Tests understanding of how BST structure relates to sorted data and the divide-and-conquer pattern.
BST Iterator (LeetCode 173)
MediumImplement an iterator that returns BST elements in sorted order with O(h) space and O(1) amortized time per next() call. Tests iterative in-order traversal using an explicit stack.
BST vs Other Data Structures
Understanding when to use a BST versus alternatives is crucial for both interviews and system design. The key tradeoff is between sorted-order operations and raw lookup speed.
| Feature | Sorted Array | BST |
|---|---|---|
| Search | O(log n) binary search | O(log n) balanced BST |
| Insert | O(n) — must shift elements | O(log n) balanced BST |
| Delete | O(n) — must shift elements | O(log n) balanced BST |
| Find Min/Max | O(1) if sorted ends known | O(log n) — follow left/right |
| Range Query | O(log n + k) binary search | O(log n + k) in-order |
| Sorted Iteration | O(n) — already in order | O(n) — in-order traversal |
| Memory Overhead | None (contiguous) | 2-3 pointers per node |
| Worst Case Guarantee | O(log n) search always | O(n) unless self-balancing |
When to Use a BST
Use a BST when you need a sorted dynamic collection that supports efficient insert, delete, and search — something sorted arrays cannot do efficiently due to shifting. BSTs shine when the problem requires ordered operations alongside mutations.
Ordered Map / Set
C++ std::map/std::set and Java TreeMap/TreeSet are implemented as self-balancing BSTs (Red-Black trees). They provide O(log n) insert, delete, and search PLUS ordered iteration, floor/ceiling queries, and range operations — capabilities hash maps lack.
Database Indexing
B-Trees (a generalization of BSTs optimized for disk I/O) power database indexes in MySQL, PostgreSQL, SQLite, and MongoDB. They enable O(log n) lookups on billions of rows and efficient range scans (e.g., WHERE price BETWEEN 10 AND 50).
Interval and Range Problems
Augmented BSTs (like interval trees and segment trees) solve range-based problems efficiently: finding overlapping intervals, range sum queries, and sweep-line algorithms. These are advanced interview topics at companies like Google and Meta.
Common Mistakes to Avoid
Validating BST by Checking Only Immediate Children
The most classic BST mistake: checking only node.left < node < node.right. A tree with root 10, left child 5, and left-right grandchild 15 satisfies immediate-child checks but violates the BST property (15 > 10 but is in the left subtree). Always pass min/max bounds through recursion.
Forgetting the Degenerate Case
Claiming "BST search is O(log n)" without qualification is incorrect. Inserting sorted data (1, 2, 3, 4, 5) creates a right-skewed chain with O(n) height. Always mention worst-case O(n) and that self-balancing BSTs (AVL, Red-Black) are needed for guaranteed O(log n).
Incorrect Delete Implementation
BST deletion has subtle edge cases: deleting the root, handling the successor's right child during Case 3, and correctly updating parent pointers. Many candidates only handle Case 1 (leaf) and Case 2 (one child) but fumble Case 3 (two children). Practice the full implementation until it is second nature.
Confusing BST with Binary Heap
A BST orders left < node < right (in-order). A binary heap orders parent ≤ children (level-order). They are different data structures with different use cases. BSTs support search; heaps support extract-min/max. You cannot binary-search a heap, and a heap's in-order traversal is not sorted.