DSA problem
Range Sum of BST
Given the root of a binary search tree and two integers low and high, return the sum of the values of all nodes whose values lie in the inclusive range [low, high].
The naive approach traverses the entire tree and adds up every node whose value is in range. That is correct and easy to write, but it ignores the BST ordering invariant and always touches all n nodes — wasteful when the range covers only a small slice of the tree.
The BST property lets us prune entire subtrees during the traversal. If the current node's value is strictly less than low, every value in its left subtree is even smaller, so we can skip the left subtree completely and only recurse right. Symmetrically, if the value is strictly greater than high, we skip the right subtree and only recurse left.
The optimal solution combines a DFS walk with this pruning. At each node: if node.val < low, recurse only on the right child; if node.val > high, recurse only on the left child; otherwise add node.val to the sum and recurse on both children. This visits the minimum set of nodes that could possibly contribute, running in O(n) time in the worst case but typically much faster, with O(h) recursion stack.
Examples
root = [10,5,15,3,7,null,18], low = 7, high = 1532root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 1023root = [1], low = 1, high = 11Constraints
- The number of nodes in the tree is in the range [1, 2 * 10^4].
- 1 <= Node.val <= 10^5
- 1 <= low <= high <= 10^5
- All Node.val are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.