Binary Search Trees — Order From Structure

A BST is a binary tree with one constraint that makes it useful: the left subtree of any node contains only values strictly less than that node, and the right subtree contains only values strictly greater. This sounds simple. The way it traps people: “less than” means all descendants, not just direct children. Get that wrong and you’ll write a BST validator that passes 90% of test cases and fails quietly on the ones that matter.

Get the property precisely right, and everything else — insert, delete, search, validation — follows from the same invariant.

The BST Property (Stated Precisely)

For every node N: all values in N’s left subtree are strictly less than N.val. All values in N’s right subtree are strictly greater than N.val. This holds recursively for every node in the tree.

The classic trap:

      5
     / \
    1   4
       / \
      3   6

A naive check passes: 4 < 5 (left of 5), 3 < 4, 6 > 4. But this is not a valid BST. Node 4 is in the right subtree of 5, so it must be greater than 5. It isn’t.

The fix: propagate valid bounds as you descend.

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

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

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

Use Long.MIN_VALUE and Long.MAX_VALUE as initial bounds to correctly handle nodes with integer extreme values. If you use Integer.MIN_VALUE, a node with value Integer.MIN_VALUE incorrectly fails the lower bound check.

What most people get wrong: checking only parent-child relationships instead of carrying bounds all the way down. The bounds are inherited constraints — every ancestor imposes a restriction on every descendant.

Core Operations: Insert, Search, Delete

All three operations cost O(h) where h is the height of the tree. In a balanced BST, h = O(log n). In a degenerate BST, h = O(n). This distinction matters — see the degenerate BST section below.

Search — O(h)

Follow the BST property: if target < current, go left; if target > current, go right; if equal, found.

TreeNode search(TreeNode node, int target) {
    if (node == null)          return null;    // not found
    if (node.val == target)    return node;    // found
    if (target < node.val)
        return search(node.left,  target);
    else
        return search(node.right, target);
}

Insert — O(h)

A new value always lands at a leaf position. Follow search logic to find where it belongs, then place it there.

TreeNode insert(TreeNode node, int val) {
    if (node == null) return new TreeNode(val);   // base case: place here
    if (val < node.val)
        node.left  = insert(node.left,  val);
    else if (val > node.val)
        node.right = insert(node.right, val);
    // val == node.val: duplicate — ignore or handle per problem spec
    return node;
}

The return node at the end is essential. Without it, you’d build the new subtree but detach it from its parent.

Delete — O(h)

Three cases based on how many children the target node has:

  1. No children: just remove the node (return null to parent)

  2. One child: replace the node with its sole child

  3. Two children: find the in-order successor (smallest value in right subtree), copy its value to the current node, then delete the successor from the right subtree

TreeNode delete(TreeNode node, int val) {
    if (node == null) return null;

    if (val < node.val) {
        node.left  = delete(node.left,  val);
    } else if (val > node.val) {
        node.right = delete(node.right, val);
    } else {
        // Found the node to delete
        if (node.left  == null) return node.right;   // cases 1 and 2
        if (node.right == null) return node.left;    // case 2

        // Case 3: replace value with in-order successor, delete successor
        TreeNode successor = findMin(node.right);
        node.val   = successor.val;
        node.right = delete(node.right, successor.val);
    }
    return node;
}

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

Why the in-order successor preserves the BST property: the successor is the smallest value in the right subtree, meaning it’s greater than everything in the left subtree and smaller than all other elements in the right subtree. It’s the only value that can legally occupy the deleted node’s position.

Inorder Traversal = Sorted Output

This is non-obvious but consequential: in a BST, inorder traversal (left → node → right) visits all nodes in ascending sorted order. The BST property guarantees it at every node — your left subtree is smaller, you are the middle, your right subtree is larger. Applied recursively, this gives a globally sorted sequence.

This single fact unlocks a category of problems:

// Find kth smallest element — iterative inorder
int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    int count = 0;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        count++;
        if (count == k) return curr.val;
        curr = curr.right;
    }
    return -1; // k > number of nodes
}

Similarly, to find the kth largest: reverse inorder (right → node → left) gives descending order.

Degenerate BST — The O(n) Disaster

Insert elements in sorted order (1, 2, 3, 4, 5…) into a BST and you get this:

1
 \
  2
   \
    3
     \
      4
       \
        5

Height = n. Every operation degrades to O(n). You’ve built a linked list with extra steps and extra pointer overhead.

This is why self-balancing trees exist in production. Java’s TreeMap and TreeSet use Red-Black trees internally — they guarantee O(log n) operations regardless of insertion order. When you use TreeMap in an interview solution, you’re implicitly relying on O(log n) guarantees. State that explicitly.

AVL Tree Intuition — Rotations (Conceptual)

An AVL tree maintains: for every node, |height(left) - height(right)| ≤ 1. After each insert or delete, it checks this and fixes violations using rotations.

You don’t need to implement rotations for LeetCode. You need to understand what they do:

Left rotation (fixes right-heavy imbalance):

    A              B
     \            / \
      B    →     A   C
       \
        C

Right rotation (fixes left-heavy imbalance):

      A          B
     /          / \
    B    →     C   A
   /
  C

Left-right and right-left rotations are double rotations (rotate child first, then root). Each rotation is O(1) — three pointer reassignments. After the rotation, the local subtree is balanced again.

For deep implementation: CLRS Chapter 13. For interview prep: know the 4 types exist, know they’re O(1), and know why the BST property is preserved after each.

Common BST Problems

Recover BST (LC 99)

Two nodes in a valid BST were swapped. Find them and swap back. The approach: inorder traversal of the corrupted BST produces a sequence with inversions (points where a value is larger than the next). There will be one or two inversions:

  • Two inversions: first node is the left element of the first inversion; second node is the right element of the last inversion

  • One inversion (adjacent swap): both nodes are the pair in the single inversion

BST to Greater Sum Tree (LC 1038)

Replace each node’s value with the sum of all values greater than or equal to it. Solution: reverse inorder traversal (right → node → left) carrying a running sum. O(n), one pass, no extra space.

int runningSum = 0;

void reverseInorder(TreeNode node) {
    if (node == null) return;
    reverseInorder(node.right);          // visit larger values first
    runningSum += node.val;
    node.val = runningSum;
    reverseInorder(node.left);
}

Practice Problems

#

Problem

Difficulty

Key Insight

1

LC 700 — Search in BST

Easy

Direct BST property application

2

LC 701 — Insert into BST

Easy

Insert at leaf, return root unchanged

3

LC 98 — Validate BST

Medium

Propagate min/max bounds down

4

LC 230 — Kth Smallest in BST

Medium

Inorder traversal = sorted order

5

LC 1038 — BST to Greater Sum Tree

Medium

Reverse inorder + running sum

6

LC 99 — Recover BST

Hard

Find inversions in inorder sequence

For problem 3 (Validate BST): solve it with the bounds propagation technique. The inorder approach also works, but bounds propagation is more fundamental — it’s what you’d use if asked to validate programmatically in a system that doesn’t allow full traversal.