Trimming a Binary Search Tree

Given a Binary Search Tree (BST) and a valid range [low, high], the task is to trim the tree so that all node values fall within this inclusive range. The structure of the resulting tree should maintain BST properties.

A common mistake is to simply return null when encountering a node outside the range:

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

This approach fails because it discards entire subtrees. When a node falls below the minimum bound, its right subtree may still contain valid nodes. Similarly, when a node exceeds the maximum bound, its left subtree might have valid values within range.

The correct approach handles each case specifically:

• If the current node's value is less than low, recursively process and return the right subtree
• If the current node's value is greater than high, recursively process and return the left subtree
• Otherwise, keep the node and recursively trim both subtrees

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) 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;
    }
};

Constructing a Balanced BST from Sorted Array

When converting a sorted array into a height-balanced BST, the key insight is that the middle element should serve as the root to ensure balanced subtrees. A height-balanced tree has a height difference of at most one between left and right subtrees for every node.

Using array indices rather than creating subarrays avoids unnecessary memory allocation:

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

The midpoint calculation uses start + (end - start) / 2 to prevent integer overflow that could occur with (start + end) / 2 when both indices are large.

Converting BST to Greater Sum Tree

For this problem, each node's value must be updated to the sum of all values greater than or equal to it. In a BST, an in-order traversal yields values in ascending order. Therefore, a reverse in-order traversal (right, root, left) processes nodes in descending order.

Traversing right-to-left allows accumulating the sum as we go:

class Solution {
private:
    int cumulativeSum = 0;
    
    void reverseInorder(TreeNode* node) {
        if (!node) return;
        
        reverseInorder(node->right);
        
        cumulativeSum += node->val;
        node->val = cumulativeSum;
        
        reverseInorder(node->left);
    }
    
public:
    TreeNode* convertBST(TreeNode* root) {
        cumulativeSum = 0;
        reverseInorder(root);
        return root;
    }
};

This approach maintains a running sum of all nodes visited so far. Since the traversal visits nodes in descending order, each node receives the cumulative sum of itself and all larger values that came before it.