938. Range Sum of BST
Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Recursion
FAANG asked: 1
Acceptance rate: 83.2%
Problem Breakdown
The problem requires calculating the sum of all node values within a specified range [low, high] in a binary search tree (BST). The inputs are:
root: The root node of the BST.low: The lower bound of the range.high: The upper bound of the range.
The output is an integer representing the sum of all node values that fall within the inclusive range [low, high].
Implicit constraints and edge cases include:
- The tree can be empty (though the problem guarantees at least one node).
- All node values are unique.
- Node values are in the range
[1, 10^5]. lowandhighare within the same range as node values.
Intuition
A brute-force approach would involve traversing all nodes in the tree and summing those that fall within the specified range. This approach has a time complexity of O(n), where n is the number of nodes, since we potentially visit every node.
However, leveraging the properties of a BST can lead to a more efficient solution. In a BST:
- All values in the left subtree are less than the root.
- All values in the right subtree are greater than the root.
This property allows us to skip entire subtrees if they fall completely outside the range [low, high], thus reducing unnecessary node visits.
Approach
We will use a recursive depth-first search (DFS) approach to traverse the tree. The key insight is:
- If the current node’s value is less than
low, we only need to explore the right subtree. - If the current node’s value is greater than
high, we only need to explore the left subtree. - If the current node’s value is within the range
[low, high], we add its value to the sum and explore both subtrees.
This approach ensures that we only visit nodes that could potentially contribute to the sum, reducing the number of unnecessary visits compared to a brute-force traversal.
Complexity Analysis
- Time Complexity: O(n) in the worst case, where n is the number of nodes. This occurs when the tree is unbalanced and resembles a linked list.
- Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case (unbalanced tree), this can be O(n).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rangeSumBST(root: TreeNode, low: int, high: int) -> int:
if not root:
return 0
# If the current node's value is less than low, explore only the right subtree
if root.val < low:
return rangeSumBST(root.right, low, high)
# If the current node's value is greater than high, explore only the left subtree
elif root.val > high:
return rangeSumBST(root.left, low, high)
# Otherwise, include this node's value and explore both subtrees
else:
return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)
Edge Cases Handled
- Empty Tree: The function returns 0 immediately if the
rootisNone. - Single Node Tree: If the tree has only one node, it checks whether that node’s value is within the range and returns its value accordingly.
- Unbalanced Tree: The solution handles unbalanced trees efficiently by leveraging the BST properties to skip unnecessary subtree traversals.