Top 12 Binary Search Tree Interview Problems: The Patterns Behind Each One

Every language ships a sorted map. Java has TreeMap. Python has SortedList. You could go years building real systems without ever touching a raw BST node. And yet here you are, interview morning, about to implement deletion.

What interviewers are actually testing is simpler than you think: do you understand the BST property well enough to exploit it, avoid its traps, and build on top of it when the obvious approach is too slow? Not whether you can recite it from memory. Whether you can think with it.

These 12 problems cover the must-know patterns. Work through them in order and you build a mental model, not a solution bank.

The One Insight That Makes Half These Problems Trivial

Inorder traversal of a BST produces keys in sorted order. Not interesting trivia. Genuinely load-bearing.

Roughly half the problems below are sorted-array problems running on a BST in disguise. Before writing a single line, ask: if this input were a sorted array, would the answer be obvious? If yes, inorder traversal is almost certainly the path. Keep this lens active and you will save yourself a lot of wrong turns and at least one embarrassing O(n²) solution.

1. Search in a BST (LC 700, Easy)

The entry point. Given a target value, return the subtree rooted at the matching node.

def searchBST(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return searchBST(root.left, val)
    return searchBST(root.right, val)

The BST property eliminates half the remaining tree at every step, giving O(h) time. For a balanced tree that's O(log n). For a degenerate chain it's O(n). Every BST problem involving traversal uses this same left/right decision. This one is the pure form. If this feels too easy, good. It's supposed to. It's the foundation for everything else.

2. Range Sum of BST (LC 938, Easy)

Sum all node values between low and high, inclusive.

def rangeSumBST(root, low, high):
    if not root:
        return 0
    total = root.val if low <= root.val <= high else 0
    if root.val > low:
        total += rangeSumBST(root.left, low, high)
    if root.val < high:
        total += rangeSumBST(root.right, low, high)
    return total

Prune via the BST property. If root.val <= low, every node in the left subtree is also below range, so skip the entire subtree. The worst case is still O(n) but you touch far fewer nodes in practice. Any problem with range constraints on a BST almost always wants this approach.

3. Minimum Absolute Difference in BST (LC 530, Easy)

Find the minimum absolute difference between any two nodes.

def getMinimumDifference(root):
    prev = None
    min_diff = float('inf')

    def inorder(node):
        nonlocal prev, min_diff
        if not node:
            return
        inorder(node.left)
        if prev is not None:
            min_diff = min(min_diff, node.val - prev)
        prev = node.val
        inorder(node.right)

    inorder(root)
    return min_diff

Inorder gives sorted order, so the minimum difference is always between adjacent nodes in the traversal. No need to compare all pairs. Track a single prev variable and update as you go. Without the inorder insight this looks O(n²). With it, O(n). That gap is the entire point of recognizing the pattern.

4. Lowest Common Ancestor of a BST (LC 235, Medium)

Find the LCA of two nodes p and q. This is the problem where knowing it's a BST, not just a binary tree, cuts your code in half.

def lowestCommonAncestor(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    return root

In a general binary tree, LCA requires O(n) DFS. In a BST it's O(h) because the split point is immediately readable from the values. If both nodes are smaller than root, recurse left. If both are larger, recurse right. Otherwise root is the LCA. No visited set, no post-order logic, no tracking parent pointers. Three lines of conditions.

5. Validate Binary Search Tree (LC 98, Medium)

Determine whether a binary tree is a valid BST. This one has a trap in it and the trap catches a lot of people.

def isValidBST(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (isValidBST(root.left, min_val, root.val) and
            isValidBST(root.right, root.val, max_val))

The classic mistake: comparing a node only to its immediate parent. It fails on the first counterexample you would think of if you stopped to think. A node in the right subtree must be greater than every ancestor it branched left from, not just its direct parent. The fix is to propagate bounds downward: every node must sit strictly inside (min_val, max_val). This bounds-propagation pattern applies any time you need to verify a structural invariant recursively.

Checking only the parent is like checking your ID at a venue by asking "are you 21?" with no ID. It's technically a check. It is not the check.

6. Kth Smallest Element in a BST (LC 230, Medium)

Return the kth smallest value (1-indexed). Sorted-array problem in disguise: in a sorted array, just return index k-1.

def kthSmallest(root, k):
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

Inorder with early exit. The iterative form lets you stop mid-traversal without visiting the rest of the tree. The interesting follow-up: if the BST is modified often and kth smallest is queried often, augment each node with a size field. That gives O(log n) per query instead of O(n). See order-statistics trees for that path.

7. Insert into a BST (LC 701, Medium)

Insert a value and return the modified root.

def insertIntoBST(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    else:
        root.right = insertIntoBST(root.right, val)
    return root

BST insertion always lands at a null leaf. The recursion descends until it finds the correct empty slot, inserts there, and unwinds. Clean. This is also the reason BST operations degrade on sorted input: every insert goes to the same side and you get a linked list. You tried very hard to maintain a data structure and produced the worst version of it. That degradation is why balanced BSTs like AVL and red-black trees exist.

8. Delete Node in a BST (LC 450, Medium)

Delete a node with a given key and return the root. Deletion is harder than insertion, which is true in both BSTs and life.

def deleteNode(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)
    return root

Zero or one child is straightforward. The two-child case is the crux: replace the deleted node's value with its inorder successor (the leftmost node of the right subtree), then delete that successor from the right subtree. You can also use the inorder predecessor. Either preserves the BST property. Candidates who code too fast declare done after handling the zero/one-child case and forget the third branch entirely.

9. Convert Sorted Array to BST (LC 108, Easy)

Given a sorted array, build a height-balanced BST.

def sortedArrayToBST(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid + 1:])
    return root

Always pick the midpoint as root. This makes left and right subtrees equal in size, guaranteeing a balanced result. The structure mirrors binary search: the same halving logic that searches in O(log n) also builds in O(n). If you've internalized binary search, this problem writes itself.

10. BST Iterator (LC 173, Medium)

Implement next() (returns the next smallest) and hasNext() using O(h) memory. The interesting constraint is the memory bound: you can't just run inorder and store the whole result.

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def hasNext(self):
        return bool(self.stack)

Controlled inorder traversal: instead of running inorder all at once, you pause mid-execution using an explicit stack. Push all left children, pop one, then push that node's right subtree's left spine. Each next() call is O(1) amortized. This pattern is reusable wherever you need lazy, interruptible traversal of a sorted structure. It is also the merge step in All Elements in Two Binary Search Trees (LC 1305).

11. Convert BST to Greater Sum Tree (LC 1038 / LC 538, Medium)

Replace each node's value with the sum of all values greater than or equal to it.

def bstToGst(root):
    running_sum = 0

    def reverse_inorder(node):
        nonlocal running_sum
        if not node:
            return
        reverse_inorder(node.right)
        running_sum += node.val
        node.val = running_sum
        reverse_inorder(node.left)

    reverse_inorder(root)
    return root

Reverse inorder (right, root, left) processes nodes from largest to smallest. A running sum accumulates all values seen so far, so when you visit a node, running_sum already holds the total of every value greater than it. One pass, one variable. Any problem that needs suffix sums on a BST maps to this pattern.

12. Recover BST (LC 99, Hard)

Exactly two nodes in a BST are swapped by mistake. Restore the tree without changing its structure.

def recoverTree(root):
    first = second = prev = None

    def inorder(node):
        nonlocal first, second, prev
        if not node:
            return
        inorder(node.left)
        if prev and prev.val > node.val:
            if not first:
                first = prev
            second = node
        prev = node
        inorder(node.right)

    inorder(root)
    first.val, second.val = second.val, first.val

In a valid BST, inorder gives a sorted sequence. Two swapped nodes create at most two inversions. Adjacent swap: one inversion, first is the larger node, second is the smaller. Non-adjacent swap: two inversions, take the first node from the first inversion and the second node from the second. LC 99 catches everyone who hasn't thought carefully about this. Then it catches everyone who has, but forgot the adjacent-swap single-inversion case.

Always update first only on the first inversion. Always update second on every inversion. The O(1) space version replaces the recursive call with Morris traversal, threading back-pointers through the tree to avoid the call stack entirely.

The Five Patterns Across These 12 Problems

Pattern	Problems
Inorder = sorted	530, 230, 173, 1038, 99
BST property for O(h) navigation	700, 938, 235
Bounds propagation	98
BST modification (insert/delete)	701, 450
Construction from sorted input	108

Inorder traversal is the dominant pattern, appearing in five of the twelve. If you can write iterative inorder without thinking (see the iterative inorder walkthrough), the medium-difficulty problems collapse into mechanical applications of a single template.

The only genuinely hard problem here is LC 99. The difficulty is not the algorithm. It is recognizing that "two swapped nodes" means "at most two inversions in the inorder sequence," then handling adjacent and non-adjacent cases without branching the logic. One if not first check does all the work.

For a deeper look at the BST fundamentals underlying all of these, the BST reference covers search, insert, delete, and the theoretical bounds in detail.

What Gets You to Strong Hire on BST Problems

Most candidates know the inorder insight but apply it reactively. They reach for it after staring at the problem for two minutes. What separates a hire from a strong hire is narrating why you chose inorder before you write the first line. "Since inorder gives sorted order, I can treat this as a sorted array problem" is one sentence that signals pattern recognition. Without it, even a correct solution reads as memorized rather than understood.

The bounds-propagation trap in LC 98 catches candidates who code before they think. The two-child deletion in LC 450 catches candidates who declare done too early. LC 99 catches everyone who has not seen the one-vs-two inversion case.

To practice these under real interview conditions with live feedback on your reasoning, SpaceComplexity runs BST problems as voice-based mock interviews scored on communication, problem-solving, and code quality.