Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None
        if root.val < low:
            return self.trimBST(root.right, low, high)
        if root.val > high:
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
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;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        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;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {TreeNode}
 */
var trimBST = function(root, low, high) {
    if (!root) return null;
    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;
};
      

Problem Description

You are given the root of a binary search tree (BST) and two integer values, low and high. Your task is to "trim" the tree so that all its elements lie in the inclusive range [low, high]. Any node with a value less than low must be removed, as well as any node with a value greater than high. The resulting tree should still be a valid BST, and you should return the new root of this trimmed tree.

• You must not create new nodes; reuse the existing nodes of the tree.
• There is only one unique answer for each input.
• All values in the tree are unique.

Thought Process

At first glance, it might seem tempting to traverse the entire tree and simply delete nodes that do not fit in the range [low, high]. However, since the tree is a BST, we can take advantage of its properties to optimize the process.

In a BST, for any node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values. This means:

• If a node’s value is less than low, all nodes in its left subtree are also less than low and should be removed.
• Similarly, if a node’s value is greater than high, all nodes in its right subtree are also greater than high and should be removed.

With this in mind, we can avoid unnecessary traversals and directly prune large portions of the tree.

Solution Approach

We use a recursive approach to trim the BST efficiently:

1. Base Case: If the current node is null, return null.
2. Node Value Less Than low:
   • Since all nodes in the left subtree are even smaller, we can skip the left subtree entirely.
   • Recursively trim the right subtree and return its result.
3. Node Value Greater Than high:
   • All nodes in the right subtree are even larger, so we skip the right subtree.
   • Recursively trim the left subtree and return its result.
4. Node Value Within Range:
   • Recursively trim both left and right subtrees.
   • Set the returned results as the node’s new left and right children, respectively.
   • Return the current node.

This approach ensures we only process relevant parts of the tree and avoid unnecessary work, thanks to the BST structure.

Example Walkthrough

Consider the following BST and the range low = 1, high = 3:

        3
       / \
      0   4
       \
        2
       /
      1
  

1. Start at root (3): 3 is within [1, 3], so we trim its left and right subtrees.
2. Left child (0): 0 < 1, so we trim its right subtree (skip the left).
3. Right child of 0 is 2: 2 is in range, so we trim its left and right.
4. Left child of 2 is 1: 1 is in range, so we trim its left and right (both null).
5. 2's right is null.
6. So, 2's left is 1, right is null. 0's right becomes 2. 0 is out of range, so we replace 0 with its right subtree (2).
7. Back to root 3: right child is 4, which is > 3, so we trim its left subtree (which is null), and replace 4 with null.
8. Final tree:

           3
          /
         2
        /
       1
       

All nodes now have values within [1, 3], and the BST property is preserved.

Time and Space Complexity

Brute-force approach: If we performed a full traversal and built a new tree, the time complexity would be O(N), and space complexity O(N) due to creating new nodes.

Optimized approach (as above):

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited at most once.
• Space Complexity: O(H), where H is the height of the tree (for recursion stack). In the worst case (completely unbalanced), H = N; in the best case (balanced), H = log N.

We do not create new nodes, so extra space is only needed for recursion.

Summary

By leveraging the properties of a binary search tree, we can efficiently trim nodes outside the desired range with a simple recursive algorithm. The key insight is to skip entire subtrees when a node is out of range, rather than checking every node individually. This results in an elegant and efficient solution that preserves the BST property and only requires O(N) time and O(H) space.