Trimming a Binary Search Tree (LeetCode 669)

The algorithm removes all nodes not within the range [low, high]. The key insight is the nested recursion: when the current node's value is outside the range, one entire subtree can be discarded, but the other subtree may still contain out-of-range nodes and must be recursively trimmed.

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        if (root->val < low) return trimBST(root->right, low, high);
        if (root->val > high) return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

Explanation: If root->val < low, the entire left subtree (including root) is eliminated; only the right subtree might have valid nodes. Similarly for root->val > high. When the root is in range, we recursively trim both children.

Converting Sorted Array to Height-Balanced BST (LeetCode 108)

A height-balanced BST minimizes depth. With a sorted array, the middle element becomes the root, and the left and right halves recursively form the left and right subtrees.

class Solution {
private:
    TreeNode* build(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = build(nums, left, mid - 1);
        node->right = build(nums, mid + 1, right);
        return node;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }
};

Explanation: Using inclusive indices simplifies the recursion. The mid calculation avoids overflow. Each recursive call handles a contiguous subarray.

Converting BST to Greater Sum Tree (LeetCode 538)

A Greater Sum Tree replaces each node's value with the sum of all nodes greater than or equal to it in the original BST. This requires a reverse in-order traversal (right → root → left), accumulating values from the largest downwards.

class Solution {
private:
    int accum = 0;
    TreeNode* traverse(TreeNode* root) {
        if (root == nullptr) return nullptr;
        root->right = traverse(root->right);
        root->val += accum;
        accum = root->val;
        root->left = traverse(root->left);
        return root;
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        return traverse(root);
    }
};

Explanation: accum tracks the running sum of all visited nodes (which are larger due to reverse order). For each node, we add the current accum, then update accum to include this node's new value. The traversal returns the (modified) root, allowing chaining.