Range Sum of BST

Easy Trees & BST BST Basics Original on LeetCode

Reported atMeta

Range Sum of BST is a easy trees & bst problem solved with the bst basics pattern. The best approach, optimal (prune with the bst property, iterative), runs in O(h + m) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (visit every node) up.

Problem

You are given the root of a binary search tree and two integers low and high. Return the sum of the values of all nodes whose value lies in the inclusive range [low, high].

Examples

Example 1

Input
root = [20, 10, 30, 5, 15, 25, 35], low = 12, high = 27
Output
60
Why
Only 15, 20 and 25 lie between 12 and 27, and 15 + 20 + 25 = 60.

Example 2

Input
root = [8, 4, 12, 2, 6, 10, 14, 1], low = 1, high = 5
Output
7
Why
The values 1, 2 and 4 are in range; the whole right subtree of 8 can be skipped.

Example 3

Input
root = [50], low = 60, high = 70
Output
0
Why
No value falls inside the range, so the sum is empty.

Constraints

  • The tree has 1 to 2 · 10^4 nodes.
  • 1 <= Node.val <= 10^5, all values distinct.
  • 1 <= low <= high <= 10^5
  • root is a valid binary search tree, and the answer fits in a 32-bit signed integer.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (visit every node)O(n)O(h)
Optimal (prune with the BST property, iterative)O(h + m)O(h)

1Brute force (visit every node)

TimeO(n)Every one of the n nodes is visited, even those far outside the range.
SpaceO(h)Recursion depth equals the tree height h.

Ignore the ordering and walk the whole tree. Each node whose value is between low and high (inclusive) contributes its value.

  1. If node is null, return 0.
  2. Add node.val if low <= node.val <= high.
  3. Return that plus the results for both children.
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        int self = (root.val >= low && root.val <= high) ? root.val : 0;
        return self + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}

2Optimal (prune with the BST property, iterative)

TimeO(h + m)Only the m nodes inside the range and the nodes on the paths that bound the range (O(h)) are visited; in the worst case that is still O(n).
SpaceO(h)The stack holds at most about one pending node per level plus the current node's siblings.

In a BST everything in the left subtree is smaller than the node and everything in the right subtree is larger. So a left subtree can only contain in-range values when node.val > low, and a right subtree only when node.val < high. Use an explicit stack, add in-range values and push only the children that can still matter. The work is proportional to the nodes in range plus the two boundary paths.

  1. Push root. While the stack is not empty, pop a node (skip null).
  2. If low <= node.val <= high, add it to the sum.
  3. If node.val > low, push node.left. If node.val < high, push node.right.
  4. Return the sum.
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.val >= low && node.val <= high) sum += node.val;
            if (node.val > low && node.left != null) stack.push(node.left);
            if (node.val < high && node.right != null) stack.push(node.right);
        }
        return sum;
    }
}

Edge cases to test

  • low and high equal to the same node value
  • The range covers every node
  • The range lies completely outside the values in the tree
  • A skewed tree (a long chain)
  • Range bounds that are not values in the tree

Hints

Hint 1

The simplest correct answer: visit every node and add the values that are inside [low, high].

Hint 2

Use the BST ordering. If a node's value is below low, can anything in its left subtree be in range?

Hint 3

Only go left when node.val > low and only go right when node.val < high. This skips whole subtrees outside the range.

FAQ

What is the best time complexity for Range Sum of BST?

Optimal (prune with the BST property, iterative) runs in O(h + m) time and O(h) extra space. Only the m nodes inside the range and the nodes on the paths that bound the range (O(h)) are visited; in the worst case that is still O(n).

Which pattern does Range Sum of BST use?

It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.

Is there a brute force solution for Range Sum of BST?

Yes. Brute force (visit every node) takes O(n) time and O(h) space. Ignore the ordering and walk the whole tree.

Which edge cases should I test for Range Sum of BST?

low and high equal to the same node value; The range covers every node; The range lies completely outside the values in the tree; A skewed tree (a long chain); Range bounds that are not values in the tree.