Trimming Binary Search Trees

Problem: Given the root of a BST along with minimum boundary minBound and maximum boundary maxBound, trim the tree so that all remaining node values fall within [minBound, maxBound]. The trimming operation should preserve the relative structure of retained elements. Return the new root of the trimmed BST.

Approach: Since BSTs maintain sorted order, when a node's value falls outside the specified range, we can leverage the ordering property. If a node's value is less than the lower bound, we discard it and continue with its right subtree. Conversely, if the value exceeds the upper bound, we discard it and proceed with the left subtree.

Implementation:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int dataValue;
 *     TreeNode leftChild;
 *     TreeNode rightChild;
 *     TreeNode() {}
 *     TreeNode(int dataValue) { this.dataValue = dataValue; }
 *     TreeNode(int dataValue, TreeNode leftChild, TreeNode rightChild) {
 *         this.dataValue = dataValue;
 *         this.leftChild = leftChild;
 *         this.rightChild = rightChild;
 *     }
 * }
 */
class BSTTrimmer {
    public TreeNode trimTree(TreeNode root, int minBound, int maxBound) {
        if (root == null) {
            return null;
        }
        
        if (root.dataValue < minBound) {
            return trimTree(root.rightChild, minBound, maxBound);
        }
        
        if (root.dataValue > maxBound) {
            return trimTree(root.leftChild, minBound, maxBound);
        }
        
        root.leftChild = trimTree(root.leftChild, minBound, maxBound);
        root.rightChild = trimTree(root.rightChild, minBound, maxBound);
        return root;
    }
}

Converting Sorted Arrays to Balanced BSTs

Problem: Convert a sorted integer array into a height-balanced binary search tree.

Approach: A balanced BST can be constructed by selecting the middle element as the root, then recursively building left and right subtrees from the remaining portions of the array.

Implementation:

class ArrayToBSTConverter {
    public TreeNode convertSortedArray(int[] inputArray) {
        if (inputArray == null || inputArray.length == 0) {
            return null;
        }
        return buildTree(inputArray, 0, inputArray.length - 1);
    }

    private TreeNode buildTree(int[] arr, int start, int end) {
        if (start > end) {
            return null;
        }
        
        int middleIndex = start + (end - start) / 2;
        TreeNode currentRoot = new TreeNode(arr[middleIndex]);
        currentRoot.leftChild = buildTree(arr, start, middleIndex - 1);
        currentRoot.rightChild = buildTree(arr, middleIndex + 1, end);
        
        return currentRoot;
    }
}

Transforming BST to Greater Sum Tree

Problem: Convert a BST to a Greater Sum Tree where each node's value becomes the sum of all values greater than or equal to the original node value.

Approach: Since BSTs represent sorted data, we need to process nodes in descending order. This means traversing in reverse inorder (right-root-left) to accumulate sums from largest to smallest values.

Implementation:

class BSTToSumTreeConverter {
    private int runningTotal;

    public TreeNode transformToSumTree(TreeNode root) {
        runningTotal = 0;
        traverseAndAccumulate(root);
        return root;
    }

    private void traverseAndAccumulate(TreeNode node) {
        if (node == null) {
            return;
        }
        
        traverseAndAccumulate(node.rightChild);
        runningTotal += node.dataValue;
        node.dataValue = runningTotal;
        traverseAndAccumulate(node.leftChild);
    }
}