Range Sum of BST

Easy

#0892Time: O(N), where N is the total number of nodes in the tree. This is because we must visit every single node to check its value.Space: O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N). For a balanced tree, it would be O(log N).

Algorithms

Depth-First Search

Data structures

Tree Binary Tree Binary Search Tree

Prompt

Given the root node 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].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

Constraints:

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves traversing the entire binary tree, node by node, without taking advantage of the Binary Search Tree (BST) properties. For each visited node, we check if its value falls within the given range [low, high]. If it does, we add its value to a running total. Any standard tree traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) can be used.

Algorithm

Initialize a global or instance variable sum to 0.
Define a recursive function dfs(node, low, high).
Base Case: If the node is null, simply return.
Processing: Check if the current node.val is within the inclusive range [low, high].
If node.val >= low && node.val <= high, add node.val to the sum.
Recursive Step: Unconditionally make recursive calls for both the left and right children: dfs(node.left, low, high) and dfs(node.right, low, high).
Start the process by calling dfs(root, low, high) from the main function.
Return the final sum.

Walkthrough

We can implement this using a recursive Depth-First Search (DFS).

We define a helper function that takes a node as input. The base case for the recursion is when the node is null. In the recursive step, we first check if the current node's value is within the inclusive range [low, high]. If it is, we add the value to our sum. Crucially, we then unconditionally make recursive calls for the left and right children of the current node, ensuring every node is visited.

This process continues until all nodes have been visited. The final sum is then returned.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int sum = 0;18 19    public int rangeSumBST(TreeNode root, int low, int high) {20        dfs(root, low, high);21        return sum;22    }23 24    private void dfs(TreeNode node, int low, int high) {25        if (node == null) {26            return;27        }28        if (node.val >= low && node.val <= high) {29            sum += node.val;30        }31        // Unconditionally traverse left and right subtrees32        dfs(node.left, low, high);33        dfs(node.right, low, high);34    }35}

Complexity

Time

O(N), where N is the total number of nodes in the tree. This is because we must visit every single node to check its value.

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N). For a balanced tree, it would be O(log N).

Trade-offs

Pros

Very simple to understand and implement.
It is a general solution that works for any binary tree, not just a BST.

Cons

Highly inefficient as it fails to use the ordering property of the BST.
It explores subtrees that cannot possibly contain values in the desired range, performing unnecessary work.

This approach leverages the fundamental property of a Binary Search Tree (BST) to significantly improve efficiency. The property states that for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. By using this property, we can "prune" entire subtrees from our search if we know they cannot contain values within the [low, high] range.

Algorithm

Recursive Approach:

If the current node is null, return 0.
If node.val < low, it means all values in the left subtree are also less than low. So, we only need to search in the right subtree. Return rangeSumBST(node.right, low, high).
If node.val > high, it means all values in the right subtree are also greater than high. So, we only need to search in the left subtree. Return rangeSumBST(node.left, low, high).
If low <= node.val <= high, the current node is in the range. Its value must be added to the sum. We still need to check both left and right subtrees for other valid nodes. Return node.val + rangeSumBST(node.left, low, high) + rangeSumBST(node.right, low, high).

Iterative Approach (DFS with Stack):

Initialize sum = 0 and a stack. Push the root node.
Loop while the stack is not empty.
Pop a node from the stack.
If the node is not null:
If node.val is within [low, high], add node.val to sum.
If node.val > low, push the left child onto the stack (as it might be in range).
If node.val < high, push the right child onto the stack (as it might be in range).
After the loop, return sum.

Walkthrough

We traverse the tree, but at each node, we make an intelligent decision about where to go next based on the BST property.

If the current node's value is less than low, we know that the current node and its entire left subtree are too small. Therefore, we only need to explore the right subtree.
If the current node's value is greater than high, we know that the current node and its entire right subtree are too large. Therefore, 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 our sum. Since values in both the left and right subtrees could potentially also be in the range, we must explore both subtrees.

This pruning strategy avoids visiting nodes that are guaranteed to be outside the range, making the traversal much faster on average. This can be implemented both recursively and iteratively.

Recursive Implementation

The recursive function returns the sum of the valid nodes in the subtree rooted at the current node.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int rangeSumBST(TreeNode root, int low, int high) {18        if (root == null) {19            return 0;20        }21 22        // If current node's value is too high, search only in the left subtree23        if (root.val > high) {24            return rangeSumBST(root.left, low, high);25        }26 27        // If current node's value is too low, search only in the right subtree28        if (root.val < low) {29            return rangeSumBST(root.right, low, high);30        }31 32        // If current node's value is in range, add it to the sum33        // and explore both subtrees for other possible values in range.34        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);35    }36}

Iterative Implementation (using a Stack for DFS)

This version avoids recursion, which can be beneficial for extremely deep trees to prevent stack overflow.

1class Solution {2    public int rangeSumBST(TreeNode root, int low, int high) {3        int sum = 0;4        if (root == null) {5            return sum;6        }7        Stack<TreeNode> stack = new Stack<>();8        stack.push(root);9 10        while (!stack.isEmpty()) {11            TreeNode node = stack.pop();12            if (node != null) {13                // If node is in range, add its value14                if (node.val >= low && node.val <= high) {15                    sum += node.val;16                }17                // If current node's value is greater than low, its left child might be in range18                if (node.val > low) {19                    stack.push(node.left);20                }21                // If current node's value is less than high, its right child might be in range22                if (node.val < high) {23                    stack.push(node.right);24                }25            }26        }27        return sum;28    }29}

Complexity

Time

O(N) in the worst case, where N is the number of nodes. This happens when the range `[low, high]` includes all nodes in the tree. However, on average, the performance is much better. The number of visited nodes is proportional to the height of the tree plus the number of nodes whose values are in the range, i.e., O(H + K), where H is the tree height and K is the number of nodes in the range.

Space

O(H), where H is the height of the tree. For the recursive approach, this is the depth of the recursion stack. For the iterative approach, this is the maximum size of the stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).

Trade-offs

Pros

Significantly more efficient on average than the brute-force approach.
Effectively utilizes the core properties of a BST to prune the search space.
The solution is clean and logical.

Cons

The recursive version could theoretically cause a stack overflow on an extremely deep, unbalanced tree, although this is unlikely given the problem constraints.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int RangeSumBST ( TreeNode root , int low , int high ) { return dfs ( root , low , high ); } private int dfs ( TreeNode root , int low , int high ) { if ( root == null ) { return 0 ; } int x = root . val ; int ans = low <= x && x <= high ? x : 0 ; if ( x > low ) { ans += dfs ( root . left , low , high ); } if ( x < high ) { ans += dfs ( root . right , low , high ); } return ans ; } }

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int rangeSumBST ( TreeNode root , int low , int high ) { if ( root == null ) { return 0 ; } if ( low <= root . val && root . val <= high ) { return root . val + rangeSumBST ( root . left , low , high ) + rangeSumBST ( root . right , low , high ); } else if ( root . val < low ) { return rangeSumBST ( root . right , low , high ); } else { return rangeSumBST ( root . left , low , high ); } } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int rangeSumBST ( TreeNode * root , int low , int high ) { if ( root == nullptr ) return 0 ; if ( low <= root -> val && root -> val <= high ) { return root -> val + rangeSumBST ( root -> left , low , high ) + rangeSumBST ( root -> right , low , high ); } else if ( root -> val < low ) { return rangeSumBST ( root -> right , low , high ); } else { return rangeSumBST ( root -> left , low , high ); } } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def rangeSumBST ( self , root : TreeNode , low : int , high : int ) -> int : def search ( node ): if not node : return if low <= node . val <= high : self . ans += node . val search ( node . left ) search ( node . right ) elif node . val < low : search ( node . right ) elif node . val > high : search ( node . left ) self . ans = 0 search ( root ) return self . ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem