Binary Search Tree Interview Questions and Answers
Last updated 2026-11-19
A binary search tree stores smaller values on the left and larger on the right, which lets search, insert and delete run in O(h). Interviewers use it to test whether you really use the ordering property or just treat the structure as any tree.
Below are problems from easy to hard, each with the reasoning, Python and Java code, complexity and the edge cases people miss. Java snippets assume a TreeNode with val, left and right. For plain tree recursion first, start with binary tree interview questions.
| Key property | Inorder traversal is sorted |
|---|---|
| Typical cost | O(h), which is O(log n) when balanced |
| Worst case | O(n) on a skewed tree |
| Languages | Python and Java |
The pattern and when to spot it
Whenever the input says BST, ask how the ordering can shrink the work. Searching, range queries, floor and ceiling, lowest common ancestor and successor all discard a whole subtree at each step. Questions about sorted order, such as kth smallest or two-sum, point to inorder traversal, which gives values in ascending order without sorting.
If the input is a sorted array and you must build a tree, pick the middle as root to keep it balanced. A plain BST has no balancing, so always state that worst-case height is n for sorted insertions and name self-balancing trees such as AVL or red-black as the fix.
Common pitfalls
- Validating a BST by comparing only parent and child. Use an interval that tightens as you descend.
- Using int bounds when node values can be Integer.MIN_VALUE or MAX_VALUE.
- Forgetting how duplicates are handled. Ask the interviewer and state your rule.
- Claiming O(log n) without saying the tree must be balanced.
Binary Search Tree Interview Questions and Answers: questions with worked answers
1 Search for a value in a BST
easyCompare the target with the current node and go left or right, discarding half of the remaining tree the way binary search does. Iteration avoids recursion overhead. Time O(h), space O(1) iterative. Edge cases: empty tree, target absent, a skewed tree where h equals n and search is O(n).
pythondef search(root, key): while root and root.val != key: root = root.left if key < root.val else root.right return rootjavaTreeNode search(TreeNode root, int key) { while (root != null && root.val != key) root = key < root.val ? root.left : root.right; return root; }2 Insert a value into a BST
easyWalk down as in search until you fall off the tree, then attach a new node at that null slot. Returning the node from the recursion lets the parent relink it. Time O(h), space O(h) recursive. Edge cases: empty tree (new node becomes root), duplicates (decide a rule: ignore or send right), inserting ascending values degrades to a chain.
pythondef insert(root, key): if not root: return TreeNode(key) if key < root.val: root.left = insert(root.left, key) elif key > root.val: root.right = insert(root.right, key) return rootjavaTreeNode insert(TreeNode root, int key) { if (root == null) return new TreeNode(key); if (key < root.val) root.left = insert(root.left, key); else if (key > root.val) root.right = insert(root.right, key); return root; }3 Sum of values in a range [lo, hi]
easyUse the ordering to prune. If the node is below lo, only the right subtree can contain valid values. If above hi, only the left can. Otherwise add the node and visit both sides. Time O(n) worst case, less with pruning, space O(h). Edge cases: range outside all values, lo equal to hi, inclusive bounds.
pythondef range_sum(root, lo, hi): if not root: return 0 if root.val < lo: return range_sum(root.right, lo, hi) if root.val > hi: return range_sum(root.left, lo, hi) return root.val + range_sum(root.left, lo, hi) + range_sum(root.right, lo, hi)javaint rangeSum(TreeNode root, int lo, int hi) { if (root == null) return 0; if (root.val < lo) return rangeSum(root.right, lo, hi); if (root.val > hi) return rangeSum(root.left, lo, hi); return root.val + rangeSum(root.left, lo, hi) + rangeSum(root.right, lo, hi); }4 Validate a binary search tree
mediumComparing a node only with its children is the classic wrong answer, because a deep right descendant can be smaller than an ancestor. Pass an open interval (low, high) down: going left tightens high to the node value, going right tightens low. Time O(n), space O(h). Edge cases: values equal to Integer.MIN_VALUE or MAX_VALUE (use Long bounds or null bounds), duplicates (strict inequality rejects them), single node.
pythondef is_valid_bst(root, lo=float('-inf'), hi=float('inf')): if not root: return True if not (lo < root.val < hi): return False return is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi)javaboolean isValidBST(TreeNode root) { return ok(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean ok(TreeNode n, long lo, long hi) { if (n == null) return true; if (n.val <= lo || n.val >= hi) return false; return ok(n.left, lo, n.val) && ok(n.right, n.val, hi); }5 Kth smallest element in a BST
mediumInorder traversal of a BST yields sorted order. Walk iteratively with a stack and stop after popping k nodes, so you never touch the rest of the tree. Time O(h + k), space O(h). Edge cases: k equal to 1, k equal to n, k larger than n (decide to throw or return a sentinel). If the tree is modified often, store subtree sizes in each node for O(h) queries.
pythondef kth_smallest(root, k): stack, cur = [], root while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() k -= 1 if k == 0: return cur.val cur = cur.rightjavaint kthSmallest(TreeNode root, int k) { Deque<TreeNode> st = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !st.isEmpty()) { while (cur != null) { st.push(cur); cur = cur.left; } cur = st.pop(); if (--k == 0) return cur.val; cur = cur.right; } return -1; }6 Lowest common ancestor in a BST
mediumThe ordering gives a shortcut. If both values are smaller than the node, go left. If both are larger, go right. Otherwise the node splits them (or equals one) and is the answer. Time O(h), space O(1). Edge cases: one value is the ancestor of the other, both values equal, nodes absent from the tree.
pythondef lca_bst(root, p, q): while root: if p < root.val and q < root.val: root = root.left elif p > root.val and q > root.val: root = root.right else: return rootjavaTreeNode lcaBst(TreeNode root, int p, int q) { while (root != null) { if (p < root.val && q < root.val) root = root.left; else if (p > root.val && q > root.val) root = root.right; else return root; } return null; }7 Convert a sorted array to a height-balanced BST
mediumPick the middle element as root so both halves differ in size by at most one, then build the left and right subtrees from the two halves recursively. Time O(n), space O(log n) recursion. Edge cases: empty array, one element, even length (either middle is acceptable, mention which).
pythondef sorted_to_bst(a): def build(lo, hi): if lo > hi: return None mid = (lo + hi) // 2 node = TreeNode(a[mid]) node.left = build(lo, mid - 1) node.right = build(mid + 1, hi) return node return build(0, len(a) - 1)javaTreeNode sortedToBst(int[] a) { return build(a, 0, a.length - 1); } private TreeNode build(int[] a, int lo, int hi) { if (lo > hi) return null; int mid = lo + (hi - lo) / 2; TreeNode n = new TreeNode(a[mid]); n.left = build(a, lo, mid - 1); n.right = build(a, mid + 1, hi); return n; }8 Inorder successor of a node
mediumIf the node has a right child, the successor is the leftmost node of that subtree. Otherwise it is the lowest ancestor for which the node lies in the left subtree, found by walking from the root and remembering the last node where you turned left. Time O(h), space O(1). Edge cases: the maximum node has no successor (return null), node with no right child, target value not present.
pythondef successor(root, target): succ = None while root: if target < root.val: succ = root root = root.left else: root = root.right return succjavaTreeNode successor(TreeNode root, int target) { TreeNode succ = null; while (root != null) { if (target < root.val) { succ = root; root = root.left; } else root = root.right; } return succ; }9 Delete a node from a BST
mediumThree cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children takes the value of its inorder successor (smallest in the right subtree), and then the successor is deleted from the right subtree. Time O(h), space O(h). Edge cases: deleting the root, key not present (tree unchanged), the node with two children whose successor is its own right child.
pythondef delete(root, key): if not root: return None if key < root.val: root.left = delete(root.left, key) elif key > root.val: root.right = delete(root.right, key) else: if not root.left: return root.right if not root.right: return root.left s = root.right while s.left: s = s.left root.val = s.val root.right = delete(root.right, s.val) return rootjavaTreeNode 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; if (root.right == null) return root.left; TreeNode s = root.right; while (s.left != null) s = s.left; root.val = s.val; root.right = delete(root.right, s.val); } return root; }10 Two-sum in a BST
mediumCollect the inorder traversal into a sorted list and run two pointers, or use a hash set while traversing. The sorted-list version makes the ordering explicit and uses no hashing. Time O(n), space O(n). Edge cases: fewer than two nodes, using the same node twice for k equal to double its value, negative values.
pythondef find_target(root, k): vals = [] def inorder(n): if n: inorder(n.left); vals.append(n.val); inorder(n.right) inorder(root) i, j = 0, len(vals) - 1 while i < j: s = vals[i] + vals[j] if s == k: return True if s < k: i += 1 else: j -= 1 return Falsejavaboolean findTarget(TreeNode root, int k) { List<Integer> v = new ArrayList<>(); inorder(root, v); int i = 0, j = v.size() - 1; while (i < j) { int s = v.get(i) + v.get(j); if (s == k) return true; if (s < k) i++; else j--; } return false; } private void inorder(TreeNode n, List<Integer> v) { if (n == null) return; inorder(n.left, v); v.add(n.val); inorder(n.right, v); }11 Recover a BST in which two nodes were swapped
hardAn inorder traversal of a valid BST is increasing. With two nodes swapped there are one or two descents. Track the previous node: the first descent marks first = prev, and the last descent marks second = current. Swap the two values at the end. Time O(n), space O(h). Edge cases: swapped nodes adjacent in inorder (only one descent), swap involving the root, duplicate-free assumption.
pythondef recover(root): first = second = prev = None def inorder(n): nonlocal first, second, prev if not n: return inorder(n.left) if prev and prev.val > n.val: if not first: first = prev second = n prev = n inorder(n.right) inorder(root) first.val, second.val = second.val, first.valjavaTreeNode first, second, prev; void recover(TreeNode root) { inorder(root); int t = first.val; first.val = second.val; second.val = t; } private void inorder(TreeNode n) { if (n == null) return; inorder(n.left); if (prev != null && prev.val > n.val) { if (first == null) first = prev; second = n; } prev = n; inorder(n.right); }12 Implement a BST iterator with O(h) memory
hardKeep a stack holding the path of left descendants. next() pops the top, pushes the left spine of its right child and returns the value. hasNext() checks that the stack is non-empty. Each node is pushed and popped once, so next() is amortised O(1). Time amortised O(1) per next, O(h) worst case, space O(h). Edge cases: calling next on an exhausted iterator, single-node tree, right-skewed tree where the stack stays tiny.
pythonclass BSTIterator: def __init__(self, root): self.st = [] self._push(root) def _push(self, n): while n: self.st.append(n) n = n.left def next(self): n = self.st.pop() self._push(n.right) return n.val def has_next(self): return bool(self.st)javaclass BSTIterator { private final Deque<TreeNode> st = new ArrayDeque<>(); BSTIterator(TreeNode root) { push(root); } private void push(TreeNode n) { while (n != null) { st.push(n); n = n.left; } } int next() { TreeNode n = st.pop(); push(n.right); return n.val; } boolean hasNext() { return !st.isEmpty(); } }
Frequently asked questions
Why is inorder traversal of a BST sorted?
Left subtree values are smaller, then the node, then right subtree values larger. Visiting left, node, right therefore emits values in ascending order at every level of the tree.
What is the time complexity of BST operations?
Search, insert and delete are O(h). That is O(log n) for a balanced tree and O(n) for a degenerate chain. Self-balancing trees keep h near log n.
How do I handle duplicates in a BST?
Pick a rule and state it: reject duplicates, store a count in each node, or always send equal keys to one side. Validation code must match the rule you choose.
Are BST questions common in online assessments?
They appear regularly, usually as validate, kth smallest or LCA. See the online assessment guide for how rounds are usually structured.
Related guides
More in DSA Interview Questions
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers