Leetcode 669. Trim a Binary Search Tree

Problem Explanation

In this problem, we are given a binary search tree. Our task is to trim the tree so that all its elements fall within a given range [L, R], both inclusive. If a node falls out of this range, then the node and its children nodes will be removed from the BST. It is also possible that the root is changed in the process. At the end, we should return the new root of this trimmed binary search tree.

Let's go through an example:

1
2
3    3
4   / \
5  0   4
6   \
7    2
8   /
9  1

Above is our given binary search tree and assuming our L=1, R=3. The solution should look like:

1
2
3      3
4     /
5   2
6  /
7 1

Approach Explanation

The approach followed here depends on the property of BSTs where the left children are smaller than the parent and right children are greater than the parent.

The method can be briefly described as:

  • If the root value is less than L, we return the trimmed right subtree.
  • If the root value is more than R, we return the trimmed left subtree.
  • If the root value is within the range, we trim both the left and right subtrees, and return the root.

This solution uses a recursive DFS (Depth-First Search) traversal to find and trim the nodes. The time complexity is O(n), where n is the number of nodes, as each node is visited once.

Python Solution

1
2python
3class Solution:
4   def trimBST(self, root, L, R):
5       if not root:
6           return None
7       if root.val < L:
8           return self.trimBST(root.right, L, R)
9       elif root.val > R:
10           return self.trimBST(root.left, L, R)
11       else:
12           root.left = self.trimBST(root.left, L, R)
13           root.right = self.trimBST(root.right, L, R)
14           return root

Java Solution

1
2java
3class Solution {
4    public TreeNode trimBST(TreeNode root, int L, int R) {
5        if(root == null) 
6            return null;
7        if(root.val < L)
8            return trimBST(root.right, L, R);
9        if(root.val > R)
10            return trimBST(root.left, L, R);
11        
12        root.left = trimBST(root.left, L, R);
13        root.right = trimBST(root.right, L, R);
14        
15        return root;
16    }
17}

Javascript Solution

1
2javascript
3class Solution {
4    trimBST(root, L, R) {
5        if(!root) 
6            return null;
7        if(root.val < L)
8            return this.trimBST(root.right, L, R);
9        if(root.val > R)
10            return this.trimBST(root.left, L, R);
11
12        root.left = this.trimBST(root.left, L, R);
13        root.right = this.trimBST(root.right, L, R);
14
15        return root;
16    }
17}

C++ Solution

1
2c++
3class Solution {
4public:
5    TreeNode* trimBST(TreeNode* root, int L, int R) {
6        if(root == NULL)
7            return NULL;
8        if(root->val < L)
9            return trimBST(root->right, L, R);
10        if(root->val > R)
11            return trimBST(root->left, L, R);
12
13        root->left = trimBST(root->left, L, R);
14        root->right = trimBST(root->right, L, R);
15
16        return root;
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public TreeNode TrimBST(TreeNode root, int L, int R) {
5        if(root == null)
6            return null;
7        if(root.val < L)
8            return TrimBST(root.right, L, R);
9        if(root.val > R)
10            return TrimBST(root.left, L, R);
11        
12        root.left = TrimBST(root.left, L, R);
13        root.right = TrimBST(root.right, L, R);
14        
15        return root;
16    }
17}

So, these are the solutions for trimming a binary search tree (BST) that ensures all its elements fall within a given range. All these solutions are similar and use the Depth-First Search (DFS) traversal to go through the tree. The solutions are provided in Python, Java, JavaScript, C++, and C# to give a better understanding and provide a detailed solution for programmers of different expertise.

Additional Tips

While these solutions are perfect for the standard scenario, you may be faced with some additional challenges for input testing and exception handling. It is advisable to add more checks for edge cases such as empty BST, BST with a single node, or BST where all nodes are out of the range.

Remember that manipulating a BST preserving its main property can be complex, and it is a good practice to visualize the tree before and after the manipulation.

Additionally, interviewers often ask for time and space complexity. For this problem, the time complexity for the solution is O(N) because in the worst case we need to visit all nodes. The space complexity is also O(N) due to the usage of recursive DFS traversal consuming stack memory equivalent to the height of the tree, which can be the number of nodes in the worst-case scenario (for a skewed tree).

Conclusion

This problem teaches us the application of DFS in BST and helps us understand how we can manipulate a BST to fit certain conditions. Identifying the property of BST (left children are < parent and right children are > parent) is an important aspect of this problem, which helps in choosing the correct algorithm to solve this problem. Good luck with your coding!


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫