## Algorithm

Problem Name: 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.

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`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
while(root && (root->val < L || root->val > R)) root = root->val < L ? root->right : root->left;
if(!root) return NULL;
root->left = trimBST(root->left, L, R);
root->right = trimBST(root->right, L, R);
return root;
}
};
``````
Copy The Code &

Input

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

Output

cmd
[1,null,2]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
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);
} else 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;
}
}
``````
Copy The Code &

Input

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

Output

cmd
[1,null,2]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const trimBST = function(root, L, R) {
return single(root, L, R);
};

function single(node, L, R) {
if (node === null) {
return null;
}
if (node.val > R) {
return single(node.left, L, R);
}
if (node.val  <  L) {
return single(node.right, L, R);
}
if (node.left !== null) {
node.left = single(node.left, L, R);
}
if (node.right !== null) {
node.right = single(node.right, L, R);
}
return node;
}
``````
Copy The Code &

Input

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

Output

cmd
[3,2,null,1]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if not root: return
root.left=self.trimBST(root.left,L,R)
root.right=self.trimBST(root.right,L,R)
if root.val>R or root.val``````
``` Copy The Code & Input x – + cmd root = [3,0,4,null,2,null,null,1], low = 1, high = 3 Output x – + cmd [3,2,null,1] ```
``` #5 Code Example with C# Programming Code - C# Programming namespace LeetCode { public class _0669_TrimABinarySearchTree { public TreeNode TrimBST(TreeNode root, int L, int R) { if (root == null) return null; if (root.val > R) return TrimBST(root.left, L, R); if (root.val < L) return TrimBST(root.right, L, R); root.left = TrimBST(root.left, L, R); root.right = TrimBST(root.right, L, R); return root; } } } Copy The Code & Input x – + cmd root = [1,0,2], low = 1, high = 2 Output x – + cmd [1,null,2] Advertisements (adsbygoogle = window.adsbygoogle || []).push({}); Demonstration ```
``` #668 Leetcode Kth Smallest Number in Multiplication Table Solution in C, C++, Java, JavaScript, Python, C# Leetcode #670 Leetcode Maximum Swap Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```