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.

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 ; } }

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