Problem Breakdown
We are given a Binary Search Tree (BST) and two integer boundaries: low and high. Our goal is to prune this tree so that every remaining node has a value within the inclusive range [low, high].
Inputs:
- A pointer/reference to the root of a BST.
- Two integers defining the valid range (
low,high).
Outputs:
- The new root of the trimmed BST (which may be different from the original input root).
Implicit Constraints & Edge Cases:
- BST Property: Crucial for optimization. For any node, all values in its left subtree are smaller than it, and all values in its right subtree are larger. This allows us to discard entire subtrees without visiting every single leaf if we know they fall outside the range.
- Empty Tree: If
rootis null initially or becomes null after pruning (all nodes removed), return None/null. - Range Coverage: It’s possible all nodes are within bounds, in which case no changes occur. Conversely, it’s possible only a subtree exists that satisfies the condition.
Intuition
A naive approach might be to traverse every node and check its value against low and high. While this works (O(N) time), we can do better by leveraging the BST structure.
Key Insight:
If the current node’s value is less than low, then all nodes in the left subtree are also less than low. We don’t need to visit them; they must be discarded entirely. The new valid root for this branch will come from the right child (if any). Similarly, if a node’s value exceeds high, all its right descendants exceed high.
This suggests a recursive strategy:
- If current node is too small (
< low), discard left and recurse on right. - If current node is too large (
> high), discard right and recurse on left. - If current node is valid, keep it but recursively trim its children with the same bounds.
Approach
- Base Case: Check if
rootis null. Return None immediately to handle empty trees or fully pruned branches. - Pruning Logic (The “Cut”):
- If
root.val < low: The current node and its entire left subtree are invalid because of BST properties. We discard the left child entirely (left = None) but we must check if a valid root exists in the right branch. So, returntrim(root.right). - If
root.val > high: Symmetric to above. Discard right child and recurse on left: returntrim(root.left).
- If
- Valid Node:
- If
low <= root.val <= high, keep the current node as part of the result tree. However, its children might still need trimming based on their own values relative to[low, high]. We recursively call trim on both left and right children and update pointers:root.left = self.trimBST(root.left) root.right = self.trimBST(root.right) return root
- If
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes. In the worst case (e.g., a skewed tree or when all nodes are valid), we visit every node once to determine if it stays or goes. However, due to BST properties, many branches are skipped entirely in constant time during recursion, making average performance better than generic traversal on non-BSTs.
- Space Complexity: O(H) for the call stack, where H is the height of the tree. In a balanced BST this is O(log N), but can degrade to O(N) in skewed cases (linked-list style).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def trimBST(self, root: 'TreeNode', low: int, high: int) -> 'TreeNode':
# Base case: empty tree or fully pruned branch returns None
if not root:
return None
# If current node is smaller than the lower bound,
# it and its entire left subtree are invalid.
# We discard them by returning the result of trimming the right child.
if root.val < low:
return self.trimBST(root.right, low, high)
# If current node is larger than the upper bound,
# it and its entire right subtree are invalid.
# Discard them by recursing on the left child.
elif root.val > high:
return self.trimBST(root.left, low, high)
# Current node is within bounds.
# We keep this node but recursively trim children to maintain structure.
else:
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
Edge Cases Handled
- Null Root: The function returns
Noneimmediately if the input tree is empty. - All Nodes Out of Range (Low): If every node value is less than
low, recursion eventually hits a null right child and propagates up, returningNone. - Root Replacement: When
root.val < low, we returntrim(root.right). This effectively replaces the root with the smallest valid ancestor found in the right subtree. - Single Node Tree: If input is
[1]and range includes 1, it returns itself; if not, it recurses on children (None), returning None or keeping node depending on bounds logic applied to that single node.