Range Sum of BST
Problem
Given the root of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
- The number of nodes in the tree is in the range [1, 2 * 10⁴]
- 1 ≤ Node.val ≤ 10⁵
- 1 ≤ low ≤ high ≤ 10⁵
- All Node.val are unique
Example
root = [10,5,15,3,7,null,18], low = 7, high = 1532Starting at the root (10), which is within [7,15], add 10 to the sum. Explore the left subtree: node 5 is less than low, so its entire left child (3) can be skipped because all values there are even smaller, but its right child (7) is within range, so add 7. Explore the right subtree: node 15 is within range, so add 15, and its right child (18) is greater than high, so skip that branch as well. The total sum is 10 + 7 + 15 = 32.
Approach
Straightforward Solution
A brute-force approach would traverse all nodes in the tree and sum those within the range, resulting in O(n) time complexity where n is the number of nodes. This is correct but can be inefficient if large subtrees are outside the range.
Core Observation
A binary search tree (BST) property guarantees that for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This property allows pruning subtrees that cannot contain values within the range [low, high].
Path to Optimal
Leveraging the BST property, the algorithm can prune traversal paths. If the current node's value is less than low, its left subtree can be skipped entirely because all values there are smaller. Similarly, if the node's value is greater than high, its right subtree can be skipped. This pruning reduces unnecessary recursive calls, improving efficiency especially for balanced trees.
Optimal Approach
Use a recursive DFS that at each node decides whether to include its value and which subtrees to explore based on comparisons with low and high. If node.val is within [low, high], add it to the sum and recurse both left and right. If node.val < low, recurse only right. If node.val > high, recurse only left. This approach guarantees visiting only nodes that could contribute to the sum, achieving better than O(n) in practice.
Time
O(n)
In the worst case, all nodes fall within the range or the tree is skewed, requiring traversal of all nodes. However, pruning can reduce the number of nodes visited in balanced trees.
Space
O(h)
The recursion stack depth is proportional to the height h of the tree. For a balanced BST, h = O(log n), but in the worst case (skewed tree), h = O(n).
Pattern Spotlight
DFS (Pruned Search on BST)
Use the BST ordering to prune entire subtrees that cannot contain valid values, reducing the search space by skipping left or right subtrees based on the current node's value relative to the range boundaries.
Solution
| 1 | class Solution: |
| 2 | def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int: |
| 3 | if not root: |
| 4 | return 0 |
| 5 | |
| 6 | ans = 0 |
| 7 | if low <= root.val <= high: |
| 8 | ans += root.val |
| 9 | if low < root.val: |
| 10 | ans += self.rangeSumBST(root.left, low, high) |
| 11 | if root.val < high: |
| 12 | ans += self.rangeSumBST(root.right, low, high) |
| 13 | |
| 14 | return ans |
Step-by-Step Solution
Return 0 Immediately for Null Nodes to Handle Base Case
| 3 | if not root: |
| 4 | return 0 |
Objective
To handle the base case of recursion by returning 0 when the current node is null, indicating no contribution to the sum.
Key Insight
The base case prevents infinite recursion and correctly terminates the search at leaf nodes. Returning 0 ensures that null branches do not affect the sum calculation.
Interview Quick-Check
Core Logic
Returning 0 for null nodes correctly terminates recursion and contributes nothing to the sum.
State & Boundaries
This base case defines the recursion boundary condition.
Accumulate Node Value if Within Range and Recursively Explore Valid Subtrees
| 6 | ans = 0 |
| 7 | if low <= root.val <= high: |
| 8 | ans += root.val |
| 9 | if low < root.val: |
| 10 | ans += self.rangeSumBST(root.left, low, high) |
| 11 | if root.val < high: |
| 12 | ans += self.rangeSumBST(root.right, low, high) |
Objective
To add the current node's value to the sum if it lies within [low, high], and recursively explore left and/or right subtrees based on BST pruning rules.
Key Insight
The BST property allows pruning: if node.val is within the range, both subtrees might contain valid nodes, so recurse both sides. If node.val is less than low, only the right subtree can contain valid nodes. If node.val is greater than high, only the left subtree can contain valid nodes. This selective recursion avoids unnecessary exploration, improving efficiency.
Interview Quick-Check
Core Logic
Use BST ordering to decide which subtrees to recurse into, pruning branches that cannot contain valid values.
State & Boundaries
Check node.val against low and high to determine recursion paths.
Common Pitfalls & Bugs
Failing to prune subtrees leads to unnecessary traversal and worse performance.
Return the Accumulated Sum for the Current Subtree
| 14 | return ans |
Objective
To return the total sum of valid nodes found in the current subtree to the caller.
Key Insight
Returning the accumulated sum allows the recursive calls to combine partial sums from left and right subtrees, building up the final answer.
Interview Quick-Check
Core Logic
Return the sum of the current node's value (if valid) plus sums from valid subtrees.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if not root:Check if the current node is null to handle the base case.
This base case prevents infinite recursion by terminating traversal at leaf nodes, ensuring the algorithm only processes valid nodes.
if low <= root.val <= high:Add the current node's value to the sum if it lies within the range [low, high].
Including the node's value only when it falls within the specified range ensures the sum reflects the problem's requirement precisely.
ans += root.valAdd the sum from the left subtree if the current node's value is greater than low.
Because the BST property guarantees all left subtree values are less than the current node's value, we only explore left if there's a chance of finding values >= low, pruning unnecessary traversal.
if root.val < high:Add the sum from the right subtree if the current node's value is less than high.
Similarly, the BST property guarantees all right subtree values are greater than the current node's value, so we only explore right if there's a chance of finding values <= high, pruning unnecessary traversal.
return 0Return 0 for null nodes, contributing nothing to the sum.
Returning zero here correctly represents that a null subtree adds no value to the range sum, maintaining correctness of the accumulation.
return ansReturn the accumulated sum for the current subtree.
Returning the sum allows recursive calls to combine partial sums from subtrees, building the final answer up the call stack.
if low < root.val:Check if the current node's value is greater than low to decide left subtree exploration.
This conditional check enables pruning by skipping the left subtree when all its values are guaranteed to be less than low, improving efficiency.
ans += self.rangeSumBST(root.left, low, high)Recursively compute the range sum for the left subtree.
This recursive call explores the left subtree to accumulate valid node values, contributing to the total sum.
ans += self.rangeSumBST(root.right, low, high)Recursively compute the range sum for the right subtree.
This recursive call explores the right subtree to accumulate valid node values, contributing to the total sum.
ans = 0Initialize the accumulator for the current subtree's sum.
Starting with zero ensures a clean slate for accumulating valid node values and recursive sums from subtrees.
Test Your Understanding
Why can we skip the left subtree when the current node's value is less than low?
Because in a BST, all values in the left subtree are less than the current node's value, so if the current node's value is already less than low, all nodes in the left subtree are guaranteed to be less than low and thus outside the range.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Range Sum of BST from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Range Sum of BST drill