Autocoder

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 propertyInorder traversal is sorted
Typical costO(h), which is O(log n) when balanced
Worst caseO(n) on a skewed tree
LanguagesPython 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

Binary Search Tree Interview Questions and Answers: questions with worked answers

  1. 1

    Search for a value in a BST

    easy

    Compare 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).

    python
    def search(root, key):
        while root and root.val != key:
            root = root.left if key < root.val else root.right
        return root
    java
    TreeNode search(TreeNode root, int key) {
        while (root != null && root.val != key)
            root = key < root.val ? root.left : root.right;
        return root;
    }
  2. 2

    Insert a value into a BST

    easy

    Walk 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.

    python
    def 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 root
    java
    TreeNode 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. 3

    Sum of values in a range [lo, hi]

    easy

    Use 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.

    python
    def 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)
    java
    int 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. 4

    Validate a binary search tree

    medium

    Comparing 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.

    python
    def 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)
    java
    boolean 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. 5

    Kth smallest element in a BST

    medium

    Inorder 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.

    python
    def 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.right
    java
    int 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. 6

    Lowest common ancestor in a BST

    medium

    The 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.

    python
    def 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 root
    java
    TreeNode 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. 7

    Convert a sorted array to a height-balanced BST

    medium

    Pick 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).

    python
    def 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)
    java
    TreeNode 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. 8

    Inorder successor of a node

    medium

    If 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.

    python
    def successor(root, target):
        succ = None
        while root:
            if target < root.val:
                succ = root
                root = root.left
            else:
                root = root.right
        return succ
    java
    TreeNode 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. 9

    Delete a node from a BST

    medium

    Three 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.

    python
    def 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 root
    java
    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;
            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. 10

    Two-sum in a BST

    medium

    Collect 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.

    python
    def 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 False
    java
    boolean 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. 11

    Recover a BST in which two nodes were swapped

    hard

    An 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.

    python
    def 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.val
    java
    TreeNode 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. 12

    Implement a BST iterator with O(h) memory

    hard

    Keep 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.

    python
    class 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)
    java
    class 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

See all in this section