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:
[1, 104].0 <= Node.val <= 104root is guaranteed to be a valid binary search tree.0 <= low <= high <= 104We can utilize the properties of a BST to perform a recursive traversal. The strategy here involves:
low, we need to trim the left subtree and consider the right subtree.high, we trim the right subtree and consider the left subtree.low, high], we recursively trim both subtrees.The recursive function trimBST checks if the node is NULL. If the node's value is less than low, it trims the left subtree. If the node's value is greater than high, it trims the right subtree. Otherwise, it recursively processes both subtrees.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once.
Space Complexity: O(h), where h is the height of the tree, representing the recursion stack.
This iterative approach uses a stack to traverse the tree. The main idea is to mimic the recursive depth-first search using an explicit stack.
Instead of using recursion, this C++ implementation uses a stack to perform depth-first search-like traversal. It adjusts the nodes based on their values compared to the bounds low and high, ensuring all nodes in the stack are within the bounds.
Java
Python
Time Complexity: O(n), as each node is processed once.
Space Complexity: O(h), where h is the height of the tree, due to the stack usage.
| Approach | Complexity |
|---|---|
| Recursive Trimming with BST Properties | Time Complexity: O(n), where n is the number of nodes in the tree, since each node is processed once. |
| Iterative Approach Using a Stack | Time Complexity: O(n), as each node is processed once. |
Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python • NeetCode • 94,636 views views
Watch 9 more video solutions →Practice Trim a Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode