Binary Search Trees
On this page
A hash map finds an exact key in O(1), but it can't answer "what is the smallest key larger than 42?" or "list everything between 10 and 20, in order" without scanning everything. A sorted array can, but inserting into it is O(n). A binary search tree keeps data sorted and supports fast inserts, by storing the order in the shape of the tree.
How it works
The ordering rule

A binary search tree (BST) is a binary tree with one rule, applied at every node: all values in the left subtree are smaller than the node, and all values in the right subtree are larger. (How duplicates are handled varies; ask, or store a count.)
Two consequences matter for interviews:
- An inorder traversal (left, node, right) visits the values in sorted order.
- At any node you know which side a value must be on, so you can discard half the remaining tree at each step, like binary search.
Search and insert follow one path

To search, start at the root and go left if the value is smaller, right if it's larger, until you find it or fall off the tree. Insert does the same walk and attaches a new leaf where the search fell off. Both cost O(h), where h is the height.
Deleting a node with two children is the only fiddly case: replace its value with its inorder successor (the smallest value in its right subtree), then delete that successor, which has at most one child.
Shape decides speed

If keys arrive in random order the tree stays roughly balanced and h is about log n. If they arrive sorted, every new key goes to the right and the tree degrades into a linked list with h = n. Self-balancing trees (red-black trees, AVL trees) rotate nodes on insert and delete to keep h = O(log n). You won't be asked to code one, but you should know the standard library uses them:
- Java
TreeMap/TreeSet, C++std::map/std::set: balanced BSTs withfloorKey,ceilingKey,lower_bound,upper_bound. - Python has no built-in balanced BST. Use
bisecton a sorted list (O(n) insert, fine for moderate sizes) or the third-partysortedcontainers.SortedList. - Go's standard library has no ordered map; use a sorted slice with
sort.Search, or write the tree.
Operations and costs
| Operation | Balanced BST | Unbalanced worst case |
|---|---|---|
| Search, insert, delete | O(log n) | O(n) |
| Minimum or maximum | O(log n) | O(n) |
| Next larger or smaller (successor) | O(log n) | O(n) |
| All values in sorted order | O(n) | O(n) |
| Values in a range [lo, hi] | O(log n + k) for k results | O(n) |
When to reach for it
- You need ordered data that changes: insert and delete while still asking for the minimum, the maximum, or the nearest value. A balanced tree (
TreeMap,std::map) is the tool. - The problem gives you a BST: use the ordering. Inorder traversal gives sorted values (k-th smallest, validate the tree); the rule tells you which side to search (lowest common ancestor, closest value).
- Hash map or BST? Hash map for exact lookups only (faster on average). BST when order matters: ranges, floor and ceiling, sorted iteration.
Example
Search, insert, and validate. Validation is the classic trap: checking only that left.val < node.val < right.val is not enough, because a value deep in the left subtree must also be smaller than every ancestor it sits left of. Pass an allowed range down instead.
def search(root, val):
node = root
while node and node.val != val:
node = node.left if val < node.val else node.right
return node
def insert(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val:
root.right = insert(root.right, val)
return root
def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
if not node:
return True
if not (lo < node.val < hi):
return False
return (is_valid_bst(node.left, lo, node.val) and
is_valid_bst(node.right, node.val, hi))
Search in the other languages:
TreeNode search(TreeNode root, int val) {
TreeNode node = root;
while (node != null && node.val != val) {
node = val < node.val ? node.left : node.right;
}
return node;
}
TreeNode* search(TreeNode* root, int val) {
TreeNode* node = root;
while (node && node->val != val) {
node = val < node->val ? node->left : node->right;
}
return node;
}
func search(root *TreeNode, val int) *TreeNode {
node := root
for node != nil && node.Val != val {
if val < node.Val {
node = node.Left
} else {
node = node.Right
}
}
return node
}
Time: O(h) for search and insert; O(n) for validation. Space: O(1) for iterative search; O(h) for the recursive functions.
Inserting 8, 3, 10, 1, 6, 14 gives the tree in the pictures, whose inorder walk is 1 3 6 8 10 14. A tree where 9 sits in the right subtree of 3, which is itself left of 8, passes the parent–child check but fails the range check, as it should.
Common mistakes
- Validating only parent and child. Pass
(lo, hi)bounds down the tree, or check that the inorder walk is strictly increasing. - Integer bounds. Using
Integer.MIN_VALUEas a sentinel breaks when a node holds that value; usenull/Longbounds or infinities. - Assuming balance. Say "O(log n) if balanced, O(n) worst case" unless the tree is guaranteed balanced.
- Ignoring duplicates. Ask whether they're allowed and which side they go on.
- Forgetting the BST property exists. If the problem says BST and your solution would work on any binary tree, you probably missed a faster approach.
Say this in the interview
- "Because it's a BST, the inorder traversal is sorted, so the k-th smallest is the k-th node I visit."
- "At each node I know which side the target is on, so the search follows one path: O(h), which is O(log n) for a balanced tree."
- "I need sorted order with inserts and deletes, so I'd use a TreeMap here instead of a hash map."
Used in
- Problems: Validate Binary Search Tree, Kth Smallest Element in a BST, Lowest Common Ancestor of a Binary Tree (simpler in a BST)
- Patterns: Tree DFS, Binary Search (the same halving idea)
- Data structures: Binary Trees, Heaps (a different ordering rule), Hash Maps