Pruning a Binary Search Tree

When removing nodes from a BST that fall outside a specified range [minVal, maxVal], the BST property must be maintained. If a node's value is less than the minimum threshold, the node and its entire left subtree are invalid. The valid result must come from the right subtree. Conversely, if a node's value exceeeds the maximum threshold, the right subtree is discarded, and the solution lies in the left subtree. If the node's value is within bounds, both subtrees are processed recursively.

class Solution {
    public TreeNode trimBST(TreeNode node, int minVal, int maxVal) {
        if (node == null) return null;
        
        if (node.val < minVal) {
            return trimBST(node.right, minVal, maxVal);
        }
        if (node.val > maxVal) {
            return trimBST(node.left, minVal, maxVal);
        }
        
        node.left = trimBST(node.left, minVal, maxVal);
        node.right = trimBST(node.right, minVal, maxVal);
        return node;
    }
}

Constructing a Balanced BST from a Sorted Array

Building a height-balanced BST from a sorted array requires consistently selecting the middle element as the root for any given subarray. This divides the array into two halves, which naturally form the left and right subtrees. The process is recursive: calculate the central index, create a node, and assign the results of the left and right subarray constructions to its children.

class Solution {
    public TreeNode sortedArrayToBST(int[] values) {
        return constructBalancedTree(values, 0, values.length - 1);
    }

    private TreeNode constructBalancedTree(int[] values, int start, int end) {
        if (start > end) return null;
        
        int center = start + (end - start) / 2;
        TreeNode current = new TreeNode(values[center]);
        
        current.left = constructBalancedTree(values, start, center - 1);
        current.right = constructBalancedTree(values, center + 1, end);
        
        return current;
    }
}

Converting a BST to a Greater Tree

To transform a BST such that every node's value is updated to the sum of all values greater than or equal to itself, a reverse in-order traversal (right-root-left) is required. This traversal visits nodes in descending order. By maintaining a running sum of encountered node values, each visited node's value can be updated by adding the accumulated sum to its original value.

class Solution {
    private int cumulativeSum = 0;

    public TreeNode convertBST(TreeNode root) {
        traverseAndAccumulate(root);
        return root;
    }

    private void traverseAndAccumulate(TreeNode node) {
        if (node == null) return;
        
        traverseAndAccumulate(node.right);
        
        cumulativeSum += node.val;
        node.val = cumulativeSum;
        
        traverseAndAccumulate(node.left);
    }
}