Trimming a Binary Search Tree

The task involves removing nodes from a binary search tree (BST) such that every remaining node's value falls within a specified range [low, high]. If the root node falls outside this range, the structure of the tree must be adjusted, potentially returning a new root.

struct TreeNode* prune_bst(struct TreeNode* node, int low, int high) {
    if (!node) {
        return NULL;
    }

    if (node->val < low) {
        // Current node is too small, discard it and process the right subtree
        return prune_bst(node->right, low, high);
    }
    if (node->val > high) {
        // Current node is too large, discard it and process the left subtree
        return prune_bst(node->left, low, high);
    }

    // Node is within range, recursively validate children
    node->left = prune_bst(node->left, low, high);
    node->right = prune_bst(node->right, low, high);
    return node;
}

This approach leverages the BST property: if a node's value is less than the minimum allowed, its entire left subtree is also guaranteed to be invalid. Conversely, if the value is greater than the maximum, the right subtree is invalid.

Converting a Sorted Array to a Balanced BST

Given an ascending array of integers, the objective is to construct a height-balanced binary search tree. A balanced tree minimizes the height, which is achieved by consistently selecting the middle element as the root.

struct TreeNode* build_bst_recursive(int* elements, int left, int right) {
    if (left > right) {
        return NULL;
    }

    // Select the middle element to maintain balance
    int mid = left + (right - left) / 2;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = elements[mid];

    // Construct left and right subtrees
    root->left = build_bst_recursive(elements, left, mid - 1);
    root->right = build_bst_recursive(elements, mid + 1, right);

    return root;
}

struct TreeNode* sorted_array_to_bst(int* nums, int numsSize) {
    return build_bst_recursive(nums, 0, numsSize - 1);
}

Transforming BST into Greater Sum Tree

This problem requires modifying a BST such that each node's new value is the sum of all values greater than or equal to the original value of that node. Since it is a BST, values greater than a node reside in its right subtree.

void reverse_inorder_accumulate(struct TreeNode* node, int* accumulator) {
    if (!node) {
        return;
    }

    // Traverse right subtree first (larger values)
    reverse_inorder_accumulate(node->right, accumulator);

    // Update current node value with the running sum
    node->val += *accumulator;
    *accumulator = node->val;

    // Traverse left subtree (smaller values)
    reverse_inorder_accumulate(node->left, accumulator);
}

struct TreeNode* convert_to_greater_tree(struct TreeNode* root) {
    int sum = 0;
    reverse_inorder_accumulate(root, &sum);
    return root;
}

The solution employs a reverse in-order traversal (right-root-left). This visits nodes in descending order, allowing a running sum to be maintained and added to each node sequentially.