Range Sum of BST
Understanding the Problem
We have a binary search tree (BST) and a range defined by low and high. We need to find every node whose value falls within that range (inclusive on both ends) and return their sum.
This is a BST, not an arbitrary binary tree. In a BST, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That ordering lets us prune entire subtrees that cannot contain values in our range. If a node's value is below low, its left subtree holds only smaller values, none of which qualify. If a node's value is above high, its right subtree holds only larger values.
Key Constraints:
Number of nodes up to 2 * 10^4: An O(n) traversal of the whole tree is acceptable. We do not need a sub-linear solution.1 <= Node.val <= 10^5: All values are positive, and the maximum possible sum is 2 10^4 10^5 = 2 10^9. This is below the 32-bit signed integer limit of about 2.147 10^9, so a standardintaccumulator does not overflow.- All
Node.valare unique, so each node contributes at most once to the sum.
Approach 1: DFS (Visit All Nodes)
Intuition
Traverse the entire tree with DFS and, at each node, check whether its value falls within [low, high]. If it does, add it to a running sum. This ignores the BST property and treats the tree as a generic binary tree, which means it works on any binary tree, not only a BST.
Algorithm
- Start a DFS traversal from the root.
- At each node, check if its value is between
lowandhigh(inclusive). - If yes, add the node's value to the sum.
- Recurse on both left and right children regardless of the node's value.
- Return the total sum.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every single node in the tree exactly once, regardless of whether it's in range or not.
- Space Complexity: O(h) where h is the height of the tree. The recursion stack goes as deep as the tree height. O(log n) for a balanced BST, O(n) for a skewed tree.
This visits every node, including subtrees that cannot contain in-range values. The next approach uses the BST ordering to skip those subtrees.
Approach 2: DFS with BST Pruning (Optimal)
Intuition
The BST property lets us skip subtrees instead of visiting them. For any node:
- If
node.val < low, then this node and everything in its left subtree is below the range, so we recurse only into the right subtree. - If
node.val > high, then this node and everything in its right subtree is above the range, so we recurse only into the left subtree. - If
low <= node.val <= high, the node is in range. We add its value and recurse into both subtrees, since the left subtree may hold values at leastlowand the right subtree may hold values at mosthigh.
Pruning skips entire branches that cannot contribute to the sum. On a balanced BST with a narrow range, the number of visited nodes drops from O(n) toward O(log n + k), where k is the count of in-range values.
The BST invariant guarantees that every value in a node's left subtree is strictly less than the node's value, and every value in its right subtree is strictly greater. When a node's value is below low, every value in its left subtree is also below low, so none of them can be in range and the entire subtree is safe to skip. The reverse holds for a node above high: its whole right subtree is above high.
Algorithm
- If the current node is null, return 0.
- If the node's value is less than
low, recurse only on the right child (left subtree is all too small). - If the node's value is greater than
high, recurse only on the left child (right subtree is all too large). - Otherwise, add the node's value and recurse on both children.
Example Walkthrough
Code
- Time Complexity: O(n) in the worst case. If every node falls within [low, high], we visit all n nodes. In practice, pruning often reduces this to O(log n + k) where k is the number of in-range nodes.
- Space Complexity: O(h) where h is the height of the tree. The recursion stack depth equals the tree height. O(log n) for a balanced BST, O(n) for a completely skewed tree.
The recursion depth equals the tree height, so a deeply skewed tree can reach a recursion depth of n. The next approach applies the same pruning iteratively with an explicit queue, which keeps the stack depth constant.
Approach 3: Iterative BFS with Pruning
Intuition
The same pruning logic works iteratively with a queue (BFS). We process nodes from the queue, add a value when it is in range, and enqueue a child only when its subtree could contain in-range values.
The decision to enqueue mirrors the recursive pruning. We enqueue the left child only when node.val > low, because if node.val <= low the entire left subtree is at most node.val and below the range. We enqueue the right child only when node.val < high, by the symmetric argument. For the constraints here (up to 2 * 10^4 nodes) recursion would not overflow the stack, but the iterative form keeps stack depth constant regardless of tree shape.
Algorithm
- Initialize a queue with the root node and a sum variable set to 0.
- While the queue is not empty, dequeue a node.
- If the node's value is in range, add it to the sum.
- If the node's value is greater than
low, enqueue the left child (it might have in-range values). - If the node's value is less than
high, enqueue the right child (it might have in-range values). - Return the sum.
Example Walkthrough
Code
- Time Complexity: O(n) in the worst case. Same as the recursive approach. We visit each relevant node once. Pruning reduces the constant factor but doesn't change the worst-case bound.
- Space Complexity: O(n). The queue can hold up to O(n) nodes in the worst case. This is worse than the recursive approach's O(h) for tall narrow trees, but avoids stack overflow on extremely deep skewed trees.