BST Operations

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

// Insert
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);
    // val == root.val: duplicate, no action
    return root;
}

// Delete
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 found
        if (root.left  == null) return root.right;
        if (root.right == null) return root.left;
        // Has two children: replace with inorder successor (min of right subtree)
        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;
}

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

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        if (--k == 0) return curr.val;
        curr = curr.right;
    }
    return -1;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left,  p, q);
    if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
    return root; // p and q are on different sides — this is the LCA
}

// BST to sorted list: inorder traversal
List<Integer> sorted = new ArrayList<>();
inorder(root, sorted);

// Sorted array to balanced BST
public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
TreeNode build(int[] nums, int l, int r) {
    if (l > r) return null;
    int mid = l + (r - l) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    node.left  = build(nums, l,     mid - 1);
    node.right = build(nums, mid + 1, r);
    return node;
}