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.
rootis 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;
}
};
Input
Output
#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;
}
}
Input
Output
#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;
}
Input
Output
#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.valInput
Output
#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;
}
}
}
Input
Output