Skip to main content
Back to Library
cracking the tech interview system design and algorithms in java 25

Binary Search Trees

10 min read Chapter 33 of 75
Summary

Covers BST property, search/insert/delete operations, validation, inorder successor/predecessor,...

Covers BST property, search/insert/delete operations, validation, inorder successor/predecessor, and conversion between BSTs and sorted arrays.

Binary Search Trees

A Binary Search Tree (BST) imposes a single rule that transforms a binary tree into an ordered data structure: for every node, all values in the left subtree are strictly less than the node’s value, and all values in the right subtree are strictly greater. This invariant — maintained across every subtree, not individual children — enables O(h) search, insertion, and deletion where h is the tree height.

BSTs appear in interviews whenever a problem demands ordered operations: finding the kth smallest element, range queries, or floor/ceiling lookups. Understanding BSTs deeply also prepares you for the self-balancing variants (AVL, Red-Black) that guarantee O(log n) performance.

The BST Property

The formal property is stronger than “left child < parent < right child.” It requires:

  • Every node in the left subtree has a value less than the current node.
  • Every node in the right subtree has a value greater than the current node.

This recursive constraint means you cannot validate a BST by checking only immediate children. A node deep in a left subtree must still be less than the subtree’s root ancestor. This distinction is the foundation of the classic “Validate BST” interview problem.

Search follows the BST invariant: if the target is less than the current node, go left; if greater, go right; if equal, found.

TreeNode search(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    if (target < root.val) return search(root.left, target);
    return search(root.right, target);
}
TreeNode searchIterative(TreeNode root, int target) {
    while (root != null && root.val != target) {
        root = (target < root.val) ? root.left : root.right;
    }
    return root;
}

Both run in O(h) time. The iterative version uses O(1) space, making it preferable in production code where stack depth is a concern.

Insertion

Insertion finds the correct null position and places the new node there, preserving the BST property:

TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);

    if (val < root.val) {
        root.left = insert(root.left, val);
    } else if (val > root.val) {
        root.right = insert(root.right, val);
    }
    // If val == root.val, duplicates are ignored

    return root;
}

This recursive approach returns the (possibly new) subtree root at each level, linking the new node into the tree. Time: O(h). Space: O(h) for the recursion stack.

Deletion

Deletion is the most complex BST operation because removing a node must preserve the BST property. Three cases arise:

Case 1 — Leaf node: Remove it directly. No children to reattach.

Case 2 — One child: Replace the node with its single child.

Case 3 — Two children: Find the inorder successor (smallest node in the right subtree), copy its value to the current node, then delete the successor from the right subtree.

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 {
        // Found the node to delete

        // Case 1 & 2: zero or one child
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;

        // Case 3: two children
        TreeNode successor = findMin(root.right);
        root.val = successor.val;
        root.right = delete(root.right, successor.val);
    }
    return root;
}

TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

The findMin helper walks left until it reaches the leftmost (smallest) node in a subtree. This is the inorder successor of the deleted node — the smallest value that is still greater than the deleted value.

Time: O(h) for all three cases. The two-children case does two O(h) operations (find successor + delete successor), but both traverse downward, so the total remains O(h).

Validate BST

The classic interview question: given a binary tree, determine whether it is a valid BST.

The trap: Checking only node.left.val < node.val < node.right.val is wrong. You must enforce bounds inherited from ancestors.

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;

    return validate(node.left, min, node.val)
        && validate(node.right, node.val, max);
}

Using long for min/max handles the edge case where node values equal Integer.MIN_VALUE or Integer.MAX_VALUE.

Alternative approach: Perform an inorder traversal and verify the result is strictly increasing. This works because inorder traversal of a valid BST produces sorted output:

boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    long prev = Long.MIN_VALUE;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        if (current.val <= prev) return false;
        prev = current.val;
        current = current.right;
    }
    return true;
}

Both approaches run in O(n) time. The min/max approach short-circuits early on invalid inputs, while the inorder approach has the advantage of not needing extra parameters.

Inorder Traversal Produces Sorted Output

This property deserves emphasis: an inorder traversal of a BST visits nodes in ascending order. This fact powers several interview solutions:

  • Validate BST: Check that inorder is sorted.
  • Kth smallest: Stop inorder traversal at the kth element.
  • Convert BST to sorted list: Run inorder, collect values.
  • Two Sum in BST: Use inorder iterator as a sorted array.

Memorize this property. It converts BST problems into sorted-array problems.

Classic Problem: Kth Smallest Element in BST

Find the kth smallest value. Inorder traversal with early termination:

int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        k--;
        if (k == 0) return current.val;
        current = current.right;
    }
    throw new IllegalArgumentException("k exceeds tree size");
}

Time: O(h + k) — descend to the leftmost node (O(h)), then visit k nodes. Space: O(h).

For repeated queries, augment each node with a size field (count of nodes in its subtree). Then the kth smallest can be found in O(h) without full traversal, similar to order-statistics trees.

Classic Problem: Convert Sorted Array to Balanced BST

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

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

TreeNode build(int[] nums, int left, int right) {
    if (left > right) return null;

    int mid = left + (right - left) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    node.left = build(nums, left, mid - 1);
    node.right = build(nums, mid + 1, right);
    return node;
}

Pick the middle element as the root — this ensures equal-sized subtrees at every level. The result is a balanced BST with height O(log n).

Time: O(n). Space: O(log n) recursion stack.

Classic Problem: Inorder Successor in BST

Find the node with the smallest value greater than a given node’s value:

TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode successor = null;

    while (root != null) {
        if (p.val < root.val) {
            successor = root;       // candidate: current node is greater
            root = root.left;       // search for a closer (smaller) candidate
        } else {
            root = root.right;      // current node is too small or equal
        }
    }
    return successor;
}

Logic: Walk the BST. Every time you go left (meaning the current node is greater than p), the current node becomes a successor candidate. Going right means the current node is too small. The last candidate when you reach null is the successor.

Time: O(h). Space: O(1).

Classic Problem: Two Sum in BST

Determine whether two nodes exist in the BST whose values sum to a target. Use two inorder iterators — one forward, one reverse — as a two-pointer technique on a sorted array:

boolean findTarget(TreeNode root, int k) {
    List<Integer> sorted = new ArrayList<>();
    inorder(root, sorted);

    int left = 0, right = sorted.size() - 1;
    while (left < right) {
        int sum = sorted.get(left) + sorted.get(right);
        if (sum == k) return true;
        if (sum < k) left++;
        else right--;
    }
    return false;
}

void inorder(TreeNode node, List<Integer> list) {
    if (node == null) return;
    inorder(node.left, list);
    list.add(node.val);
    inorder(node.right, list);
}

Time: O(n). Space: O(n) for the sorted list.

For O(h) space, implement a BST iterator that yields elements in forward order and another in reverse order. Use them as two pointers without materializing the entire sorted list.

BST vs HashMap: When BST Wins

HashMaps provide O(1) average-case lookups, so why use a BST?

OperationHashMapBST (Balanced)
Search by keyO(1) avgO(log n)
InsertO(1) avgO(log n)
DeleteO(1) avgO(log n)
Find min/maxO(n)O(log n)
Find kth smallestO(n log n)O(log n)*
Range query [lo, hi]O(n)O(log n + k)
Ordered iterationO(n log n)O(n)

*With augmented size field.

BSTs win when you need ordered operations: range queries, predecessor/successor, rank, or sorted iteration. Java’s TreeMap is a BST (specifically a Red-Black tree) and provides all these operations with guaranteed O(log n) performance.

Degenerate BSTs: Why Balancing Matters

Insert elements 1, 2, 3, 4, 5 into an empty BST. The result:

1
 \
  2
   \
    3
     \
      4
       \
        5

This is a linked list. Every operation takes O(n) instead of O(log n). The tree’s height equals n - 1 instead of log₂(n).

This degeneration happens whenever elements arrive in sorted (or nearly sorted) order. The solution: self-balancing BSTs that automatically restructure after each insertion or deletion to maintain O(log n) height. AVL trees and Red-Black trees are the two primary self-balancing BSTs, covered in the next sub-chapters.

Complexity Summary

OperationAverage CaseWorst Case (Skewed)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
InorderO(n)O(n)
SpaceO(n)O(n)

All O(log n) averages assume random insertion order. For guaranteed O(log n), use a balanced BST.

Edge Cases and Interviewer Tips

  • Duplicate values: Standard BSTs do not handle duplicates. Clarify with the interviewer: skip duplicates, allow them in one subtree, or store counts.
  • Empty tree: delete and search on null return null, not an error. Handle this cleanly.
  • Integer overflow: When validating BST with min/max bounds, use long to avoid overflow at Integer.MIN_VALUE and Integer.MAX_VALUE.
  • Recursion depth: For trees with up to 10⁵ nodes, recursion is safe. Beyond that, convert to iterative.
  • Follow-up pattern: Interviewers frequently ask “how would you make this O(log n) in all cases?” The answer: use a self-balancing BST.

State the BST property explicitly at the start of your solution. This signals to the interviewer that you understand the invariant and will not make the common mistake of checking only immediate children.