669. Trim a Binary Search Tree LeetCode Solution

In this guide, you will get 669. Trim a Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Trim a Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Trim a Binary Search Tree solution in C++
4. Trim a Binary Search Tree solution in Java
5. Trim a Binary Search Tree solution in Python
6. Additional Resources

Problem Statement of 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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

669. Trim a Binary Search Tree LeetCode Solution in C++

class Solution {
 public:
  TreeNode* trimBST(TreeNode* root, int L, int R) {
    if (root == nullptr)
      return nullptr;
    if (root->val < L)
      return trimBST(root->right, L, R);
    if (root->val > R)
      return trimBST(root->left, L, R);
    root->left = trimBST(root->left, L, R);
    root->right = trimBST(root->right, L, R);
    return root;
  }
};
/* code provided by PROGIEZ */

669. Trim a Binary Search Tree LeetCode Solution in Java

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);
    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;
  }
}
// code provided by PROGIEZ

669. Trim a Binary Search Tree LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.