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
PreviewLeveraging 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse 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…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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
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.
Return the Accumulated Sum for the Current Subtree
To return the total sum of valid nodes found in the current subtree to the caller.
2 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why can we skip the left subtree when the current node's value is less than low?
See the answer with Pro.
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