Trim A Binary Search Tree Leetcode Problem 669 [Python Solution]

In this blog guide, we’ll delve into the LeetCode problem titled Trim A Binary Search Tree It’s a medium-level problem in the Trees category and is often associated with companies like Amazon.

We’ll explore the problem, understand its constraints, and walk through the solution step by step, using Python.

By the end, you’ll have a clear understanding of how to trim a binary search tree efficiently.

Problem Overview
The problem statement presents us with a binary search tree and two boundaries: a low value and a high value.

Our task is to trim the tree so that all its elements fall within the range defined by these boundaries, [low, high].

Importantly, trimming should not alter the relative structure of the remaining elements.

In other words, the descendants of any given node should remain descendants.

Here’s a practical example to illustrate the problem:

Example 1:

Suppose we have a binary search tree with a root node of 1 and the boundaries set to low=1 and high=2. After trimming, the tree should look like this:



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

Understanding the Constraints

Before we dive into the solution, let’s make sure we understand the constraints of the problem.

These constraints help us establish the boundaries of our solution:

• The number of nodes in the tree is within the range [1, 104].
• The value of each node in the tree is unique.
• The root is guaranteed to be a valid binary search tree.
• The values of low and high are within the range [0, 104].

Trim a Binary Search Tree LeetCode Problem 669 Python Solution

Now, let’s explore a Python solution to this problem.

Efficient Python Code Solution

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return None

        if root.val > high:
            return self.trimBST(root.left, low, high)

        if root.val < low:
            return self.trimBST(root.right, low, high)

        else:
            root.left = self.trimBST(root.left, low, high)
            root.right = self.trimBST(root.right, low, high)
            return root

The provided Python code solution consists of a TreeNode class that defines the structure of a binary tree node and a function trimBST.

The function accepts the root node of the tree and the low and high boundaries.

Here’s a step-by-step explanation of the code:

1. If the root is None, we return None.

This serves as the base case for our recursive solution.

1. If the value of the root node is greater than the high boundary, it means the entire right subtree and the root node should be excluded from the result.

In this case, we call trimBST recursively on the left subtree and return the result.

1. If the value of the root node is less than the low boundary, it means the entire left subtree and the root node should be excluded from the result.

In this case, we call trimBST recursively on the right subtree and return the result.

1. If neither of the above conditions is met, it means the current root node falls within the acceptable range.

We update its left and right subtrees by calling trimBST recursively on both and then return the modified root.

This recursive approach ensures that the tree is trimmed appropriately, and the resulting tree maintains the properties of a binary search tree.

Time and Space Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree.

In the worst case, we may need to visit every node.

The space complexity is O(h), where h is the height of the tree.

In the worst case, when the tree resembles a linked list, h can be equal to n.

This space complexity arises from the function call stack.

Reasoning Behind Our Approach

We’ve discussed how the algorithm works and explored the Python solution that implements it.

The key insight here is to leverage the recursive nature of binary search trees, taking into account the boundaries to trim the tree effectively while maintaining its structure.

Related Interview Questions By Company:

• Maximum Product Subarray LeetCode
• Course Schedule II LeetCode
• Brick Wall LeetCode

Related Interview Questions By Difficulty:

• Binary Tree Maximum Path Sum LeetCode
• Balanced Binary Tree LeetCode
• Validate Binary Search Tree LeetCode

Related Interview Questions By Category:

• Course Schedule Iv LeetCode
• Insert Delete Get Random O(1) LeetCode
• Range Sum Query 2D Immutable LeetCode

Conclusion

In this blog post, we tackled the LeetCode problem Trim A Binary Search Tree We examined the problem statement, its constraints, and walked through an efficient Python solution.

By applying this solution, you can trim a binary search tree so that its elements fall within a specified range, preserving the relative structure of the tree.

If you found this explanation helpful, please like and engage for more content.

Feel free to check out our Patreon for additional support.

We hope this post has equipped you with the knowledge and skills to solve this problem and similar challenges in the world of programming and data structures.

Happy coding!