Binary Search Tree (BST) Problems: Validate, Insert, Delete, Kth Smallest and More

Binary search tree questions are binary tree questions with one extra superpower: an ordering invariant. That invariant lets you discard half the tree at every step, and it makes an inorder traversal produce sorted output. Nearly every BST interview problem uses one of those two facts. Candidates who struggle usually treat a BST as a generic tree (visiting every node when they could walk one path) or misunderstand the invariant (checking only parent and child).

This guide covers the core operations with Java and Python code, the inorder trick and its applications, navigation problems like LCA and inorder successor, and a practical overview of balanced BSTs. It assumes the traversal basics from binary tree interview problems.

The example BST used in dry runs:

The BST Property (and the Mistake Everyone Makes)

For every node x: all keys in x.left's subtree are less than x.val, and all keys in x.right's subtree are greater. The word all is the point. This tree is not a BST even though every parent-child pair looks right:

Consequences of the invariant you will use constantly:

• The minimum is the leftmost node; the maximum is the rightmost.
• Inorder traversal yields keys in ascending order.
• Searching for a key follows a single root-to-leaf path: O(h).
• The same set of keys can form many different BSTs depending on insertion order; inserting 1, 2, 3, 4, 5 in order yields a linked list of height 5.

Search and Insert in a BST

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public TreeNode search(TreeNode root, int key) {
    while (root != null && root.val != key)
        root = key < root.val ? root.left : root.right;   // discard one side each step
    return root;
}

public 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);
    // equal: already present; ignore (or follow your duplicate convention)
    return root;
}

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def search(root, key):
    while root and root.val != key:
        root = root.left if key < root.val else root.right
    return root

def insert(root, key):
    new = TreeNode(key)
    if not root:
        return new
    cur = root
    while True:                      # iterative insert: O(1) extra space
        if key < cur.val:
            if not cur.left:
                cur.left = new
                break
            cur = cur.left
        elif key > cur.val:
            if not cur.right:
                cur.right = new
                break
            cur = cur.right
        else:
            break                    # duplicate
    return root

Inserting 5 into the example tree goes 8 → left to 3 → right to 6 → left to 4 → right of 4 is empty, so 5 becomes 4's right child. New keys always become leaves.

Delete a Node From a BST (LeetCode 450)

Deletion is the most-asked BST operation because of its three cases.

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(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
        while (succ.left != null) succ = succ.left;
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);  // successor has at most one child
    }
    return root;
}

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

Dry run: delete 3 from the example tree. Node 3 has two children. Its successor is the leftmost node of the right subtree (6 → 4), so 3's value becomes 4, and we delete 4 from the subtree rooted at 6. Node 4 is a leaf, so it is removed. Result: 8's left child is 4, with children 1 and 6, and 6 now has only the right child 7. Inorder is still sorted: 1 4 6 7 8 10 13 14.

Follow-ups: using the inorder predecessor (max of left subtree) is equally valid. If node values are large objects or nodes are referenced externally, interviewers may ask you to relink nodes instead of copying values. And repeated deletions that always use the successor can skew the tree, one argument for balanced variants.

Validate a Binary Search Tree (LeetCode 98)

The wrong approach

Checking node.left.val < node.val < node.right.val at each node accepts the invalid tree shown earlier. The interviewer will hand you exactly that counterexample.

Approach 1: pass down valid ranges

Each node must lie strictly within (low, high). Going left tightens high to the parent's value; going right tightens low.

public boolean isValidBST(TreeNode root) {
    return valid(root, null, null);
}

// Integer bounds (null = unbounded) avoid the Integer.MIN_VALUE / MAX_VALUE trap
private boolean valid(TreeNode node, Integer low, Integer high) {
    if (node == null) return true;
    if (low != null && node.val <= low) return false;
    if (high != null && node.val >= high) return false;
    return valid(node.left, low, node.val) && valid(node.right, node.val, high);
}

Using Integer.MIN_VALUE and Integer.MAX_VALUE as initial bounds is a classic bug: a tree containing the value Integer.MAX_VALUE is then wrongly rejected. Use nullable bounds or long.

Approach 2: inorder must be strictly increasing

def is_valid_bst(root):
    prev = None
    stack, cur = [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if prev is not None and cur.val <= prev:   # <= rejects duplicates
            return False
        prev = cur.val
        cur = cur.right
    return True

Both are O(n) time and O(h) space. The inorder version exits early on the first violation. On the invalid example, inorder gives 4 5 3 6 7, and 3 after 5 fails immediately.

The Inorder Trick: A BST Is a Sorted Array in Disguise

Because inorder traversal of a BST is sorted, many BST problems reduce to sorted-array problems you already know:

The interview-quality versions avoid materialising the array (O(n) space) by processing nodes during the traversal with a prev pointer, using only O(h) space.

Recover a BST where two nodes were swapped (LeetCode 99)

In a sorted sequence with two elements swapped, there are one or two "drops" (prev > cur). The first swapped node is prev at the first drop; the second is cur at the last drop. If the swapped nodes are adjacent in inorder, there is only one drop and both come from it.

def recover_tree(root):
    first = second = prev = None
    stack, cur = [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if prev and prev.val > cur.val:
            if not first:
                first = prev          # first drop: the larger, misplaced element
            second = cur              # last drop: the smaller, misplaced element
        prev = cur
        cur = cur.right
    first.val, second.val = second.val, first.val

For inorder 1 6 4 3 7 (3 and 6 swapped from 1 3 4 6 7): drops at (6, 4) and (4, 3), so first = 6, second = 3. Swap them back. Morris traversal brings this to O(1) space, the official follow-up.

Kth Smallest Element in a BST (LeetCode 230)

Iterative inorder, counting down k, stopping as soon as the kth node is popped: O(h + k) time, O(h) space, and no wasted traversal of the rest of the tree.

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        if (--k == 0) return cur.val;      // kth node in sorted order
        cur = cur.right;
    }
    throw new IllegalArgumentException("k is larger than the number of nodes");
}

Dry run with k = 3 on the example tree: push 8, 3, 1; pop 1 (k = 2); pop 3 (k = 1), move to 6, push 6, 4; pop 4 (k = 0). Answer 4.

The follow-up: frequent inserts, deletes and kth queries

LeetCode's own follow-up asks what to do if the BST is modified often. Store size (number of nodes in the subtree) in every node, an "order statistic tree". Then:

def kth_smallest_augmented(node, k):
    # assumes each node has .size = 1 + size(left) + size(right)
    while node:
        left_size = node.left.size if node.left else 0
        if k == left_size + 1:
            return node.val
        if k <= left_size:
            node = node.left
        else:
            k -= left_size + 1
            node = node.right
    return None

That is O(h) per query, provided insert and delete update sizes along their path. Kth largest is the mirror: reverse inorder (right, node, left), or kth smallest with n - k + 1.

BST Navigation: LCA, Inorder Successor, Floor and Ceiling

Lowest common ancestor in a BST (LeetCode 235)

Unlike the general binary tree version, no postorder search is needed. Walk from the root: if both values are smaller, go left; if both are larger, go right; otherwise the current node is where their paths split, which is the LCA.

public TreeNode lowestCommonAncestor(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;              // split point (or one of them equals root)
    }
    return null;
}

Examples on the tree: LCA(4, 7) = 6, LCA(1, 6) = 3, LCA(4, 14) = 8. O(h) time and O(1) space. Compare with the general version in LCA of a binary tree; interviewers like asking for both and the difference.

Inorder successor (LeetCode 285)

The successor of p is the smallest key greater than p. Walk from the root: whenever you go left from a node, that node is a candidate successor.

def inorder_successor(root, p):
    succ = None
    while root:
        if p.val < root.val:
            succ = root              # candidate; look for a smaller one on the left
            root = root.left
        else:
            root = root.right
    return succ

Successor of 7 in the example is 8 (the last node where we went left), and successor of 14 is none. With parent pointers (LeetCode 510), the rule is: if p has a right subtree, take its leftmost node; otherwise climb until you come up from a left child.

Floor and ceiling

Floor(x) is the largest key ≤ x; ceiling(x) is the smallest key ≥ x. Same walk, recording candidates. For x = 5 in the example: floor 4, ceiling 6. These are exactly TreeMap.floorKey and ceilingKey in Java, and lower_bound-based lookups on std::set in C++, which many interview problems (calendar booking, stock price trackers, sliding window median) rely on.

Integer floor(TreeNode root, int x) {
    Integer ans = null;
    while (root != null) {
        if (root.val == x) return x;
        if (root.val < x) { ans = root.val; root = root.right; }  // candidate, try larger
        else root = root.left;
    }
    return ans;
}

Range Sum of BST (LeetCode 938)

Sum values within [low, high], pruning: if node.val < low, only the right subtree can contribute; if node.val > high, only the left. Trim a BST (669) uses identical pruning but returns the rebuilt subtree.

BST Iterator and Two Sum in a BST

BST Iterator (LeetCode 173)

next() and hasNext() in O(1) amortised time with O(h) memory: the iterative inorder traversal, paused between steps.

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)     # next smallest values live in the right subtree
        return node.val

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

Amortised argument: every node is pushed and popped exactly once over a full iteration, so n calls cost O(n) total even though one call can push O(h) nodes.

Two Sum IV, input is a BST (LeetCode 653)

Three answers, each a reasonable step in an interview: (1) hash set during any traversal, O(n) time and space; (2) inorder into an array, then two pointers, O(n) space; (3) two iterators, one ascending and one descending, used as two pointers, O(h) space. The third shows you can apply the iterator idea creatively, which is what the interviewer is looking for.

Build and Transform BSTs

Convert sorted array to a height-balanced BST (LeetCode 108)

public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); }

private TreeNode build(int[] a, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;          // middle element becomes the root
    TreeNode node = new TreeNode(a[mid]);
    node.left = build(a, lo, mid - 1);
    node.right = build(a, mid + 1, hi);
    return node;
}

O(n) time, O(log n) recursion depth. For a sorted linked list (109), either find the middle with fast/slow pointers each time (O(n log n)) or build in inorder order while consuming the list (O(n)).

Other transformations

• Construct BST from preorder (1008): insert with an upper bound in one pass, O(n): each value goes left while it is below the current bound.
• Convert BST to Greater Tree (538): reverse inorder with a running sum.
• Balance a BST (1382): inorder into an array, then rebuild with the sorted-array method.
• Merge two BSTs: inorder both, merge two sorted lists, rebuild. O(m + n).
• Largest BST subtree (333): postorder returning (isBST, size, min, max) for each subtree.

Balanced BSTs: AVL, Red-Black, B-Trees and What Interviews Expect

A plain BST degrades to O(n) when inserts arrive in sorted order, which is common in practice (auto-increment IDs, timestamps). Self-balancing trees restore O(log n) by rotating nodes after updates. A rotation is a local restructuring that preserves inorder order:

What interviewers actually expect: you will almost never be asked to code red-black insertion. You should know why balancing matters, what a rotation does, the AVL vs red-black trade-off (AVL: stricter balance and faster lookups; red-black: fewer rotations per update), and when to reach for TreeMap/std::set in a coding round. Database-oriented interviews follow up on why disks favour wide, shallow B+ trees; see database indexing with B-trees. For the Java collection APIs, see Java collections for DSA.

BST Operations Complexity Table

BST Practice List

BST Interview Tips

1. Ask about duplicates and the value range before coding. Both change validation and deletion.
2. Use the invariant to prune. If your BST solution visits every node for a search-style question (LCA, successor, floor), you have treated it as a plain binary tree. Interviewers notice.
3. Prefer iterative O(1)-space walks for search, LCA and successor; they are shorter and avoid recursion depth issues.
4. State complexity as O(h), then qualify: O(log n) if balanced, O(n) if skewed. That one sentence signals real understanding.
5. Bring up balanced trees when relevant: "In production I'd use a TreeMap, which is a red-black tree, to guarantee O(log n)."
6. Test with the trap tree (5, 4, 6, 3, 7) for validation and with a two-children deletion for delete.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.