Solution Explanation: Trim a Binary Search Tree

The problem asks to trim a Binary Search Tree (BST) such that only nodes with values within a given range [low, high] are retained. The relative structure of the remaining nodes should be preserved.

There are two main approaches to solve this problem:

Approach 1: Recursive Approach (DFS)

This approach uses Depth-First Search (DFS) to traverse the tree recursively. For each node:

1. Base Case: If the current node is null, return null.
2. Pruning: If the node's value is less than low, recursively trim the right subtree (since values in the left subtree will also be less than low). If the node's value is greater than high, recursively trim the left subtree (since values in the right subtree will also be greater than high).
3. Recursive Calls: Recursively trim the left and right subtrees of the current node.
4. Return: Return the current node (which is now part of the trimmed tree).

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. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N.

Approach 2: Iterative Approach

This approach iteratively trims the tree. It first adjusts the root to be within the range, then iteratively processes the left and right subtrees:

1. Root Adjustment: It repeatedly moves the root pointer to its left or right child until the root's value falls within [low, high] or the root becomes null.
2. Left Subtree Trimming: It iterates down the left subtree, removing nodes with values less than low.
3. Right Subtree Trimming: It iterates down the right subtree, removing nodes with values greater than high.

Time Complexity: O(N) in the worst case. While the loops themselves are O(H), where H is the height of the tree, in the worst case H can be N (a completely skewed tree).

Space Complexity: O(1). The approach uses a constant amount of extra space.

Code Examples (Python)

Approach 1 (Recursive):

class Solution:
    def trimBST(self, root, low, high):
        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
 

Approach 2 (Iterative):

class Solution:
    def trimBST(self, root, low, high):
        while root and (root.val < low or root.val > high):
            root = root.left if root.val > high else root.right
        if not root:
            return None
        node = root
        while node.left:
            if node.left.val < low:
                node.left = node.left.right
            else:
                node = node.left
        node = root
        while node.right:
            if node.right.val > high:
                node.right = node.right.left
            else:
                node = node.right
        return root
 

The iterative approach might appear slightly faster in some cases due to avoiding the overhead of recursive function calls, however, the overall time complexity remains the same, O(N). The recursive solution is often considered more elegant and easier to understand. The choice between them often depends on personal preference and coding style. Both approaches provide correct solutions to the problem.