Trim a Binary Search Tree

Leetcode 669. Trim a Binary Search Tree: Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer. Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Approach 1:

Intuition:- To trim a BST such that all its elements lie within a given range [low,high], we can use a recursive approach: 1.If the current node's value is less than low, trim its right subtree. 2.If the current node's value is greater than high, trim its left subtree. 3.If the current node's value is within the range, recursively trim both its left and right subtrees. Approach:- 1.Base Case: If the current node is None, return None. 2.Node Value Checks: -If the node's value is less than low, trim the right subtree (since the left subtree will also be out of range). -If the node's value is greater than high, trim the left subtree (since the right subtree will also be out of range). -If the node's value is within the range [low,high], recursively trim both its left and right subtrees. 3.Return the Updated Node: Ensure the node's children are updated to the trimmed subtrees. This approach ensures the BST is trimmed to include only the nodes within the specified range while maintaining the BST structure.

class Solution {
   public TreeNode trimBST(TreeNode node, int low, int high) {
         if(node == null)return null;

   
         node.left = trimBST(node.left, low, high);
         node.right = trimBST(node.right, low, high);

         if(node.val > high || node.val < low){
            if(node.left != null)return node.left;
            else return node.right;
         }
         else return node;
   }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

We visit each node exactly once in the worst case, where n is the number of nodes in the tree. The space complexity is determined by the depth of the recursion, which is 𝑂(ℎ), where h is the height of the tree. In the worst case, the height could be 𝑂(𝑛)

Introduction

The "Trim a Binary Search Tree" problem asks to trim a binary search tree (BST) such that all its elements lie within a specified range [low, high]. The trimming process involves removing any node that does not lie within the given range and ensuring that the resulting tree is still a valid BST.

The BST properties ensure that for any node: - All values in the left subtree are smaller. - All values in the right subtree are larger.

The problem provides the root of a BST and two integers, low and high, and requires trimming the tree so that all remaining nodes are between these two values.

Problem Statement

Given the root of a binary search tree and two integers low and high, trim the tree so that all its elements lie in the range [low, high] and return the new root of the tree.

The tree node structure is given above. The task is to return the trimmed BST that satisfies the range condition for each node.

Approach

The key observation here is that if the value of a node is outside the given range [low, high], we need to remove that node while maintaining the BST properties. We can recursively perform the trimming process using the following strategy:

• If the current node's value is less than the low value, then the entire left subtree of the node is also less than low. Hence, we should trim the left subtree and move to the right subtree.
• If the current node's value is greater than the high value, then the entire right subtree of the node is also greater than high. Hence, we should trim the right subtree and move to the left subtree.
• If the current node's value is within the range [low, high], then the node itself is valid, and we recursively trim both its left and right subtrees.

This approach ensures that only valid nodes remain in the tree while maintaining the BST properties.

Algorithm

The algorithm can be broken down into the following steps:

1. If the current node is None, return None (base case).
2. If the node's value is less than low, recursively trim the right subtree and return the result.
3. If the node's value is greater than high, recursively trim the left subtree and return the result.
4. If the node's value lies within the range, recursively trim both the left and right subtrees and return the current node as the root of the trimmed tree.

This recursive approach ensures the tree is trimmed efficiently and the BST properties are maintained.

Example

Consider the following Binary Search Tree:

               3
              / \
             0   4
            / \
          -10   2
        

If we want to trim the tree with the range [1, 3], the resulting tree would look like:

               3
              / 
             2
        

The nodes with values 0, -10, and 4 are removed, and the remaining tree lies within the range [1, 3].

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the recursion.

The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case (a skewed tree), the height is O(n), but in the best case (a balanced tree), the height is O(log n).

Optimized Approach

The approach described above is already quite efficient for trimming the BST. Since the tree is traversed once and the trimming is done in-place, there is little room for improvement in terms of time complexity. However, if the tree is extremely unbalanced, additional balancing techniques could be considered, but that would change the problem significantly.

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the tree, as each node is processed once during the recursion.

The space complexity remains O(h), where h is the height of the tree due to the recursion stack.

Conclusion

The "Trim a Binary Search Tree" problem provides an excellent example of how recursion can be used to efficiently remove unwanted nodes from a tree while preserving the BST properties. By recursively trimming the tree, we ensure that only valid nodes remain in the tree. This solution is both time and space efficient, with a time complexity of O(n) and a space complexity of O(h), where h is the height of the tree.