Trim a Binary Search Tree

Problem Statement

The task is to modify a given binary search tree (BST) such that it only contains the elements within a specified range [low, high]. In this process, known as trimming, you need to ensure that the intrinsic properties of the BST are preserved. This means the resulting tree should still adhere to the criteria that the left child node's value is less than its parent node's value, and the right child node's value is greater than its parent node's value. It is crucial that the structural hierarchy of the remaining elements, in terms of descendants, should remain unchanged after the trimming operation.

Examples

Example 1

Input:

root = [1,0,2], low = 1, high = 2

Output:

[1,null,2]

Example 2

Input:

root = [3,0,4,null,2,null,null,1], low = 1, high = 3

Output:

[3,2,null,1]

Constraints

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 104
• The value of each node in the tree is unique.
• root is guaranteed to be a valid binary search tree.
• 0 <= low <= high <= 104

Approach and Intuition

1. Use a recursive strategy to trim the tree, leveraging the properties of BST for efficient trimming.

   • Start with the root and compare its value with low and high.
   • If the root.val is less than low, then recursively trim the right subtree, since all values in the left subtree of root will also be less than low and thus outside the allowed range.
   • If the root.val is more than high, recursively trim the left subtree, as nodes in the right subtree of root will have values greater than high.

2. If root.val falls within the range [low, high], you'll need to trim both the left and right subtrees recursively:

   • The left child of the root becomes the result of the trimming operation on the original left subtree.
   • The right child of the root becomes the result of the trimming operation on the original right subtree.

3. This recursive approach processes each node at most once and efficiently decides the fate of each subtree based on its root value and the given limits low and high. The recursion base case is reaching a null node, which signals an end to that path in the tree.

The examples provided illustrate these points:

• For a tree rooted at 1 with children nodes 0 and 2 and boundaries 1 to 2, the node 0 is trimmed as it falls below the lower boundary.
• In another case, for a tree with root 3 and a child subtree rooted at 2 (having a child 1), boundaries 1 to 3 encourage the trimming of nodes beyond this range while maintaining nodes within the range along with their original hierarchical relationships.

Solutions

class Solution {
    public TreeNode pruneBST(TreeNode node, int lower, int upper) {
        if (node == null) return node;
        if (node.val > upper) return pruneBST(node.left, lower, upper);
        if (node.val < lower) return pruneBST(node.right, lower, upper);
    
        node.left = pruneBST(node.left, lower, upper);
        node.right = pruneBST(node.right, lower, upper);
        return node;
    }
}