Search, insert, delete, and validate a BST — the most-asked tree interview topic.
Published September 21, 2026
A binary search tree (BST) is a binary tree with one ordering rule: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That rule lets every operation discard half of the remaining tree at each step, just as binary search does on a sorted array, while still supporting cheap inserts and deletes, which a sorted array can't.
8
/ \
3 10 search(6): 6 < 8 → left; 6 > 3 → right; found.
/ \ \ Each comparison discards a whole subtree.
1 6 14
/ \ /
4 7 13
The catch is shape. Operations cost O(h), the tree's height. A balanced tree has h ≈ log n. Inserting already-sorted data into a plain BST produces a chain with h = n, and everything degrades to O(n). That's why production code uses self-balancing BSTs, such as red-black trees (Java's TreeMap/TreeSet) and AVL trees.
TreeNode search(TreeNode node, int target) {
while (node != null && node.val != target)
node = target < node.val ? node.left : node.right;
return node; // null if not present
}
TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val); // found the empty spot
if (val < root.val) root.left = insert(root.left, val);
else if (val > root.val) root.right = insert(root.right, val);
// equal: ignore (or count duplicates, or send them consistently to one side — decide explicitly)
return root;
}
The iterative search uses O(1) space. Recursive insert is compact, and returning the (possibly new) subtree root is a pattern that also makes delete clean.
null to its parent).TreeNode delete(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) root.left = delete(root.left, key);
else if (key > root.val) root.right = delete(root.right, key);
else {
if (root.left == null) return root.right; // cases 1 and 2
if (root.right == null) return root.left;
TreeNode succ = root.right; // case 3: smallest in the right subtree
while (succ.left != null) succ = succ.left;
root.val = succ.val;
root.right = delete(root.right, succ.val);
}
return root;
}
Checking only that each node is greater than its left child and smaller than its right child is wrong:
5
/ \
1 6 locally fine at every node,
/ \ but 3 is in 5's RIGHT subtree while being smaller than 5 → not a BST
3 7
The rule is about entire subtrees, so each node must lie within a range inherited from all of its ancestors:
boolean isValidBST(TreeNode root) {
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean valid(TreeNode node, long low, long high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false;
return valid(node.left, low, node.val) && valid(node.right, node.val, high);
}
Use long bounds (or nullable Integer) so nodes holding Integer.MIN_VALUE or MAX_VALUE aren't wrongly rejected. The alternative check is an inorder traversal that must be strictly increasing. Compare each value with the previous one, with no list needed.
K-th smallest: an inorder traversal visits values in sorted order, so stop at the k-th visit:
int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (true) {
while (cur != null) { stack.push(cur); cur = cur.left; }
cur = stack.pop();
if (--k == 0) return cur.val;
cur = cur.right;
}
}
That's O(h + k). If the tree is modified often and k-th queries are frequent, store subtree sizes in each node, and each query becomes O(h) by choosing left or right by count.
Lowest common ancestor: in a BST, the LCA of p and q is the first node, walking down from the root, that lies between them. While both are smaller, go left. While both are larger, go right. Otherwise you're at the split point:
TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (p.val < root.val && q.val < root.val) root = root.left;
else if (p.val > root.val && q.val > root.val) root = root.right;
else return root;
}
return null;
}
Floor, ceiling and range queries: "largest value ≤ x" means descending, remembering the last node where you went right. Counting or listing values in [lo, hi] means pruning subtrees that are entirely outside the range.
Build a balanced BST from a sorted array: make the middle element the root and recurse on each half. The height is ⌈log₂(n+1)⌉:
TreeNode build(int[] a, int lo, int hi) {
if (lo > hi) return null;
int mid = lo + (hi - lo) / 2;
TreeNode node = new TreeNode(a[mid]);
node.left = build(a, lo, mid - 1);
node.right = build(a, mid + 1, hi);
return node;
}
TreeMap / TreeSet (red-black trees) give guaranteed O(log n) put, get and remove, plus ordered operations: floorKey, ceilingKey, headMap, tailMap, firstKey, and iteration in key order. Reach for them whenever you need sorted data with frequent updates, such as leaderboards, time-ordered events, or interval bookings.| Operation | Balanced | Degenerate (chain) |
|---|---|---|
| Search / insert / delete | O(log n) | O(n) |
| Inorder traversal (all elements, sorted) | O(n) | O(n) |
| Min / max | O(log n) | O(n) |
Q: Why isn't comparing each node with its direct children enough to validate a BST? A: The BST rule applies to whole subtrees. A node deep in the right subtree must still be greater than every ancestor it's to the right of. Passing down (min, max) bounds, or checking that the inorder sequence is strictly increasing, captures that.
Q: What makes a BST degrade to O(n), and how is it prevented? A: Inserting keys in sorted, or nearly sorted, order builds a chain. Self-balancing trees (AVL, red-black) perform rotations during insert and delete to keep height O(log n). Randomizing the insertion order also helps in practice.
Q: When deleting a node with two children, why use the inorder successor? A: The successor is the smallest value larger than the node, so putting it in the node's place keeps everything on the left smaller and everything on the right larger. It also has no left child, so removing it from its original position is a simple case.
Q: TreeMap vs HashMap?
A: HashMap gives average O(1) lookups with no ordering. TreeMap gives O(log n) lookups but keeps keys sorted and supports floor, ceiling and range queries and ordered iteration. Choose TreeMap when order or range queries matter.
Q: How would you find the k-th smallest element quickly in a BST that changes often? A: Augment each node with the size of its subtree, and maintain it on insert, delete and rotations. At each node, compare k with the left subtree's size to decide whether the answer is left, this node, or right, adjusting k as you go. Each query is then O(h), which is O(log n) when balanced.