Binary Search Tree

A Binary Search Tree (BST) is a binary tree where for every node:

• All values in left subtree < node value
• All values in right subtree > node value

BST Node (same as TreeNode)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) { this.val = val; }
}

Visual Example

        8
       / \
      3   10
     / \\    \
    1   6    14
       / \\   /
      4   7 13

Search Operation - O(log n) average

public 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);
}

Insert Operation - O(log n) average

public 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);
    }
    return root;
}

Delete Operation - O(log n) average

Three cases:

1. Leaf node: Simply remove
2. One child: Replace with child
3. Two children: Replace with in-order successor (smallest in right subtree)

public 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 {
        // Node to delete found
        // 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;
}

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

Find Min and Max

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

public TreeNode findMax(TreeNode root) {
    while (root.right != null) root = root.right;
    return root;
}

Complexity Summary

Operation	Average	Worst (skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

The worst case occurs when the tree becomes a linked list (skewed tree).

Validate BST

Wrong approach: Just check left < node < right. Must verify entire subtree.

Correct approach: Pass valid range down.

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

private 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);
}

In-order Validation (Alternative)

private TreeNode prev = null;

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (!isValidBST(root.left)) return false;
    if (prev != null && root.val <= prev.val) return false;
    prev = root;
    return isValidBST(root.right);
}

BST to Sorted Array

In-order traversal gives sorted order:

public List<Integer> bstToArray(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

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

Sorted Array to Balanced BST

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

private TreeNode buildBST(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 = buildBST(nums, left, mid - 1);
    node.right = buildBST(nums, mid + 1, right);
    return node;
}

In-order Successor

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode successor = null;
    while (root != null) {
        if (p.val < root.val) {
            successor = root;
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return successor;
}

Key Insight

BST property enables O(log n) operations because each comparison eliminates half the tree. The in-order traversal of a BST always produces sorted output.