# Trim a Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/trim-a-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/trim-a-binary-search-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
**Companies:** [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
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.

**Example 1:**

![](https://assets.glich.co/dsa/trim-a-binary-search-tree/image0.jpg) 

**Input:** root = [1,0,2], low = 1, high = 2
**Output:** [1,null,2]

**Example 2:**

![](https://assets.glich.co/dsa/trim-a-binary-search-tree/image1.jpg) 

**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`

# Approaches
## In-order Traversal and Rebuild
This approach involves two main steps. First, we perform an in-order traversal of the binary search tree to get a sorted list of all its node values. Second, we filter this list to keep only the values within the `[low, high]` range. Finally, we construct a new, balanced binary search tree from this filtered list of values.
**Time:** O(N), where N is the number of nodes in the original tree. The in-order traversal takes O(N), filtering the list takes O(N), and building the new tree from the sorted list takes O(M), where M <= N. Thus, the total time is O(N). · **Space:** O(N). We need O(N) space to store the values from the in-order traversal and O(M) for the filtered values, where M is the number of nodes in the trimmed tree. The recursion stack for traversal and building takes O(H) and O(log M) respectively. The dominant factor is the O(N) space for the list.
**Pros:** Simple to understand and implement.; The resulting tree is balanced, which can be an advantage for subsequent operations (though not required by the problem).
**Cons:** Inefficient in terms of space. It requires extra space proportional to the number of nodes in the original tree.; Creates a completely new tree instead of modifying the existing one, which involves unnecessary object creation and memory allocation.; Does not fully leverage the BST property during the trimming phase.
### Explanation
Start by performing an in-order traversal on the input BST. This traversal visits nodes in ascending order of their values. Store these values in a dynamic array or list.
After the traversal, you will have a sorted list of all node values.
Iterate through this sorted list and create a new list containing only the elements that are greater than or equal to `low` and less than or equal to `high`.
With this filtered, sorted list, build a new BST. A common and efficient way to do this is to recursively build a balanced BST. The middle element of the current list segment becomes the root of the subtree. The elements to the left of the middle form the left subtree, and the elements to the right form the right subtree. This process is applied recursively until all elements are placed in the new tree.
The root of this newly constructed tree is the final answer.
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        List<Integer> sortedValues = new ArrayList<>();
        inorder(root, sortedValues);

        List<Integer> filteredValues = new ArrayList<>();
        for (int val : sortedValues) {
            if (val >= low && val <= high) {
                filteredValues.add(val);
            }
        }

        return buildTree(filteredValues, 0, filteredValues.size() - 1);
    }

    private void inorder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }

    private TreeNode buildTree(List<Integer> list, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = buildTree(list, start, mid - 1);
        node.right = buildTree(list, mid + 1, end);
        return node;
    }
}
```
### Algorithm
- 1. Create an empty list, `sortedValues`.
- 2. Perform an in-order traversal of the input BST. For each node visited, add its value to `sortedValues`.
- 3. Create another empty list, `filteredValues`.
- 4. Iterate through `sortedValues`. If a value is within the range `[low, high]`, add it to `filteredValues`.
- 5. Construct a new BST from `filteredValues`. This can be done recursively:
   - a. The middle element of the list becomes the root.
   - b. The left half of the list is used to build the left subtree.
   - c. The right half of the list is used to build the right subtree.
- 6. Return the root of the newly constructed tree.

## Optimal Recursive Approach
This approach uses recursion to trim the tree in-place. It leverages the properties of a Binary Search Tree (BST) to efficiently decide which parts of the tree to discard. The function recursively processes nodes, returning the new root of the valid subtree.
**Time:** O(N), where N is the number of nodes in the tree. In the worst case, we visit each node exactly once. · **Space:** O(H), where H is the height of the tree, for the recursion call stack. In a balanced tree, this is O(log N). In the worst case of a skewed tree, it can be O(N).
**Pros:** Highly efficient in both time and space.; Modifies the tree in-place by rearranging pointers, avoiding the overhead of creating new nodes.; The code is concise and elegant, directly reflecting the logic of the problem.
**Cons:** For extremely deep, unbalanced trees, the recursion depth could potentially lead to a stack overflow, though this is rare with typical constraints.
### Explanation
The core idea is to have a recursive function that takes a node and the bounds `low` and `high`, and returns the root of the trimmed subtree.
When considering a node, there are three possibilities:
1.  **`node.val < low`**: The current node's value is too small. Because it's a BST, all nodes in the left subtree are also too small and can be discarded. The correct replacement for this node must come from its right subtree, as it might contain nodes with values in the valid range. So, we make a recursive call on the right child: `trimBST(node.right, low, high)`.
2.  **`node.val > high`**: The current node's value is too large. Symmetrically, all nodes in the right subtree are also too large and can be discarded. The correct replacement must come from the left subtree. We make a recursive call on the left child: `trimBST(node.left, low, high)`.
3.  **`low <= node.val <= high`**: The current node is valid and should be kept. However, its children might not be. We need to trim the left and right subtrees. We do this by recursively calling the function on the left and right children and updating the node's `left` and `right` pointers with the results: `node.left = trimBST(node.left, low, high)` and `node.right = trimBST(node.right, low, high)`. After trimming its subtrees, the node itself is returned.
The base case for the recursion is when a node is `null`, in which case we simply return `null`.
```java
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }

        // If the root's value is less than low, the root and its left subtree are discarded.
        // The result must be in the right subtree.
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }

        // If the root's value is greater than high, the root and its right subtree are discarded.
        // The result must be in the left subtree.
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }

        // If the root's value is within the range, it's a valid node.
        // We recursively trim its left and right subtrees.
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;
    }
}
```
### Algorithm
- 1. Define a recursive function `trimBST(node, low, high)`.
- 2. **Base Case**: If `node` is `null`, return `null`.
- 3. **Recursive Step**:
   - a. If `node.val < low`, the current node and its left subtree are invalid. The valid tree must be in the right subtree. Return the result of `trimBST(node.right, low, high)`.
   - b. If `node.val > high`, the current node and its right subtree are invalid. The valid tree must be in the left subtree. Return the result of `trimBST(node.left, low, high)`.
   - c. If `low <= node.val <= high`, the current node is valid. Recursively trim its left and right subtrees by setting `node.left = trimBST(node.left, low, high)` and `node.right = trimBST(node.right, low, high)`.
   - d. Return the current `node`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode trimBST ( TreeNode root , int low , int high ) { if ( root == null ) { return root ; } if ( root . val > high ) { return trimBST ( root . left , low , high ); } if ( root . val < low ) { return trimBST ( root . right , low , high ); } root . left = trimBST ( root . left , low , high ); root . right = trimBST ( root . right , low , high ); return root ; } }
```

### JavaScript

```javascript
/** * 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) {
    function dfs(root) {
      if (!root) {
        return root;
      }
      if (root.val < low) {
        return dfs(root.right);
      }
      if (root.val > high) {
        return dfs(root.left);
      }
      root.left = dfs(root.left);
      root.right = dfs(root.right);
      return root;
    }
    return dfs(root);
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * trimBST ( TreeNode * root , int low , int high ) { if ( ! root ) return root ; if ( root -> val > high ) return trimBST ( root -> left , low , high ); if ( root -> val < low ) return trimBST ( root -> right , low , high ); root -> left = trimBST ( root -> left , low , high ); root -> right = trimBST ( root -> right , low , high ); return root ; } };
```

### Python

```python
# 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 : Optional [ TreeNode ], low : int , high : int ) -> Optional [ TreeNode ]: def dfs ( root ): if root is None : return root if root . val > high : return dfs ( root . left ) if root . val < low : return dfs ( root . right ) root . left = dfs ( root . left ) root . right = dfs ( root . right ) return root return dfs ( root )
```