What is a Binary Search Tree?
A binary search tree (BST) is a binary tree with one critical property: for every node, all values in its left subtree are smaller, and all values in its right subtree are greater (or equal). This ordering makes search, insert, and delete efficient.
Unlike a binary heap (which is always a complete tree stored in an array), a BST's shape depends entirely on the insertion order. Insert [1, 2, 3, 4, 5] and you get a straight line. Insert [3, 1, 4, 2, 5] and you get a balanced tree. The shape determines performance.
BST Operations & Time Complexity
| Operation | Average | Worst | Description |
|---|---|---|---|
| Search | O(log n) | O(n) | Compare with current node, go left or right. Repeat. |
| Insert | O(log n) | O(n) | Search for position, add as leaf node. |
| Delete | O(log n) | O(n) | Find node. Handle 3 cases: leaf, one child, two children. |
| In-order | O(n) | O(n) | Visit left, root, right. Produces sorted output. |
| Min / Max | O(log n) | O(n) | Go left for min, right for max. As deep as the tree. |
Search
Start at the root. If the target is less than the current node, go left. If greater, go right. Repeat until you find the value or hit a null. Each comparison eliminates half the remaining tree (in a balanced BST), giving O(log n) average performance.
Insert
Search for where the value should go. When you reach a null pointer, that's where the new node belongs. Insert it as a leaf. The tree grows from the bottom.
Delete (3 cases)
Deletion is the most complex BST operation and a frequent interview topic:
- 1.Leaf node , just remove it. Nothing else to fix.
- 2.One child , replace the node with its only child. The BST property is preserved.
- 3.Two children , find the in-order successor (smallest value in the right subtree), swap values, then delete the successor (which has at most one child).
In-order traversal
Visit left subtree, then the node, then the right subtree. For a BST, this produces values in ascending sorted order. This is the basis for “validate BST”, “kth smallest”, and “convert BST to sorted array” problems.
Balanced vs Unbalanced BSTs
A BST's performance depends on its height. A balanced tree with n nodes has height O(log n), giving O(log n) operations. But inserting sorted data creates a skewed tree with height O(n) , effectively a linked list.
Self-balancing BSTs fix this by automatically rebalancing after each operation:
- •AVL Tree , Strict balance (height difference of at most 1). More rotations, faster lookups.
- •Red-Black Tree , Relaxed balance (max 2x height difference). Fewer rotations, used in most standard libraries (Java TreeMap, C++ std::map).
- •B-Tree , Generalized balanced tree. Used in databases and file systems for disk-friendly access.
Common Interview Questions Using BSTs
BSTs appear in many coding interview patterns:
- •Validate BST , In-order traversal must be strictly increasing, OR recursively check each node against min/max bounds.
- •Lowest Common Ancestor , If both values are less than current, go left. If both greater, go right. Otherwise, current node is the LCA.
- •Kth smallest element , In-order traversal, counting nodes. Or augment nodes with subtree sizes for O(log n).
- •Convert sorted array to BST , Pick the middle element as root, recurse on left and right halves. Creates a balanced BST.
- •BST iterator (in-order) , Use a stack to simulate in-order traversal. next() and hasNext() in O(1) amortized.
- •Serialize and deserialize BST , Pre-order traversal to serialize. Reconstruct using value bounds.
Frequently Asked Questions
What is a binary search tree?add
A binary search tree (BST) is a binary tree where every node's left subtree contains only values less than the node, and the right subtree contains only values greater than or equal to the node. This ordering property enables efficient search, insert, and delete operations in O(log n) average time.
What is the time complexity of BST operations?add
For a balanced BST, search, insert, and delete are all O(log n). In the worst case (a skewed tree that looks like a linked list), these degrade to O(n). Self-balancing BSTs like AVL trees and red-black trees guarantee O(log n) for all operations.
How does BST deletion work with two children?add
When deleting a node with two children, you find its in-order successor (the smallest node in its right subtree), replace the node's value with the successor's value, then delete the successor node. The successor has at most one child (right), making it easier to remove.
What is an in-order traversal of a BST?add
In-order traversal visits the left subtree, then the current node, then the right subtree. For a BST, this visits nodes in ascending sorted order. It runs in O(n) time and is used to validate BST property, convert BST to sorted array, and find the kth smallest element.
What is the difference between a BST and a binary heap?add
A BST maintains a left-right ordering (left < parent < right) enabling efficient search. A binary heap maintains a parent-child ordering (parent < children in min heap) but not left-right ordering, enabling efficient min/max extraction. BSTs support search in O(log n); heaps do not. Heaps support extract-min in O(log n); finding min in a BST requires traversing to the leftmost node.