Binary Search Tree (BST): Core Operations and Classical Problems

Properties of BST

The defining characteristic of a BST is that an in-order traversal yields a strictly increasing sequence. This is the primary weapon for solving BST-related problems.

       5
      / \
     3   7
    / \   \
   2   4   8

In-order: 2, 3, 4, 5, 7, 8 (Strictly Ascending)

Fundamental Operations

Searching in BST (LeetCode 700)

TreeNode searchBST(TreeNode root, int val) {
    if (root == null) return null;
    if (val == root.val) return root;
    return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}

Insertion (LeetCode 701)

Find the first null position that satisfies the ordering property.

TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = insertIntoBST(root.left, val);
    else root.right = insertIntoBST(root.right, val);
    return root;
}

Deletion (LeetCode 450)

Deletion involves three specific scenarios:

1. Leaf Node: Remove immediately.
2. Single Child: Replace the current node with its child.
3. Two Children: Replace the current node with its In-order Successor (the minimum node in its right subtree).

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 {
        // Target node found
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // Two children: swap with right subtree minimum (successor)
        TreeNode successor = getMin(root.right);
        root.val = successor.val;
        root.right = deleteNode(root.right, successor.val);
    }
    return root;
}

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

Validation

Validate Binary Search Tree (LeetCode 98)

Common Trap: Only comparing a node to its immediate left and right children. You must enforce global upper and lower bounds for the entire subtree.

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;
    
    // Left subtree must be < current val; Right subtree must be > current val
    return validate(node.left, min, node.val) 
        && validate(node.right, node.val, max);
}

Alternative (In-order approach): Ensure the current value is always strictly greater than the previously visited node.

private long previousValue = Long.MIN_VALUE;

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

Utilizing In-order Traversal

K-th Smallest Element in a BST (LeetCode 230)

private int currentCount = 0;
private int resultValue = 0;

int kthSmallest(TreeNode root, int k) {
    traverse(root, k);
    return resultValue;
}

private void traverse(TreeNode node, int k) {
    if (node == null) return;
    traverse(node.left, k);
    if (++currentCount == k) {
        resultValue = node.val;
        return;
    }
    traverse(node.right, k);
}

Find Mode in BST (LeetCode 501)

Find the most frequent values without using extra space (O(1) space excluding the return list) by comparing values against a prev pointer during in-order traversal.

private int maxFreq = 0;
private int currentCount = 0;
private Integer prevVal = null;
private List<Integer> modeList = new ArrayList<>();

int[] findMode(TreeNode root) {
    inorder(root);
    return modeList.stream().mapToInt(i -> i).toArray();
}

private void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    
    // Process current node
    if (prevVal != null && node.val == prevVal) currentCount++;
    else currentCount = 1;
    
    if (currentCount > maxFreq) {
        maxFreq = currentCount;
        modeList.clear();
        modeList.add(node.val);
    } else if (currentCount == maxFreq) {
        modeList.add(node.val);
    }
    prevVal = node.val;
    
    inorder(node.right);
}

Construction

Convert Sorted Array to Balanced BST (LeetCode 108)

To maintain balance, recursively pick the middle element as the root.

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

private TreeNode build(int[] nums, int start, int end) {
    if (start > end) return null;
    int mid = start + (end - start) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = build(nums, start, mid - 1);
    root.right = build(nums, mid + 1, end);
    return root;
}

Convert BST to Greater Tree (LeetCode 538)

Update every node's value with the sum of all values $\ge$ itself. Perform a Reverse In-order traversal (Right $\rightarrow$ Root $\rightarrow$ Left).

private int runningTotal = 0;

TreeNode convertBST(TreeNode root) {
    if (root == null) return null;
    
    convertBST(root.right); // Process larger values first
    
    runningTotal += root.val;
    root.val = runningTotal;
    
    convertBST(root.left);
    return root;
}

Summary Table