Binary Search Tree (Operations · Validation · Conversion)

Core Properties of BST

• In-order Traversal = Strictly Ascending Sequence.
• For every node: All values in left subtree < Root value < All values in right subtree.
• Time Complexity (Search/Insert/Delete): O(log N) average; O(N) worst-case (when the tree degenerates into a linked list).

Searching in BST

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

BST Insertion (LeetCode 701)

Find the appropriate leaf or null position to maintain 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;
}

BST Deletion (LeetCode 450)

Deletion involves three scenarios:

1. Leaf Node: Simply remove it.
2. Single Child: Replace the node with its child.
3. Two Children: Find the In-order Successor (minimum value in the right subtree), swap values, and then delete that successor node.

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 {
        // Case 1 & 2: 0 or 1 child
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // Case 3: 2 children
        // Get the minimum in the right subtree
        TreeNode minNode = getMin(root.right);
        root.val = minNode.val;
        // Delete the successor
        root.right = deleteNode(root.right, minNode.val);
    }
    return root;
}

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

Validating a BST (LeetCode 98)

A common pitfall is only checking immediate children. Use range-based recursion or in-order property:

// Method 1: Range-based recursion (Cleanest)
boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long lower, long upper) {
    if (node == null) return true;
    if (node.val <= lower || node.val >= upper) return false;
    return validate(node.left, lower, node.val) 
        && validate(node.right, node.val, upper);
}

// Method 2: In-order traversal tracking previous value
private long prevVal = Long.MIN_VALUE;
boolean isValidBSTInorder(TreeNode root) {
    if (root == null) return true;
    if (!isValidBSTInorder(root.left)) return false;
    if (root.val <= prevVal) return false; // Fail if not strictly increasing
    prevVal = root.val;
    return isValidBSTInorder(root.right);
}

K-th Smallest Element in BST (LeetCode 230)

Utilize in-order traversal and stop when the k-th node is reached:

private int result = 0;
private int counter = 0;

int kthSmallest(TreeNode root, int k) {
    counter = k;
    inorder(root);
    return result;
}

private void inorder(TreeNode node) {
    if (node == null || counter == 0) return;
    inorder(node.left);
    if (--counter == 0) {
        result = node.val;
        return;
    }
    inorder(node.right);
}

Sorted Array to Balanced BST (LeetCode 108)

To ensure balance, always pick the middle element as the root:

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

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

Convert BST to Greater Tree (LeetCode 538)

Perform a Reverse In-order traversal (Right $\rightarrow$ Root $\rightarrow$ Left) to accumulate sums:

private int runningSum = 0;

TreeNode convertBST(TreeNode root) {
    if (root == null) return null;
    convertBST(root.right);
    
    // Process current node with prefix sum (ascending from the right)
    runningSum += root.val;
    root.val = runningSum;
    
    convertBST(root.left);
    return root;
}