Problem statement

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].

Example 1

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: 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: 6 + 7 + 10 = 23.

Example 3

Input: root = [5], low = 6, high = 9
Output: 0
Explanation: The only value lies outside the range.

Constraints

• 1 <= number of nodes <= 2 * 10^4
• 1 <= Node.val <= 10^5
• 1 <= low <= high <= 10^5
• all node values are distinct

Hints for Range Sum of BST

1. Hint 1

   Visiting every node and adding the ones in range works — but the tree is ordered, so some subtrees cannot contribute at all.

2. Hint 2

   If a node's value is at most low, nothing in its left subtree can be in range; if it is at least high, nothing in its right subtree can.

3. Hint 3

   Do a depth-first search that adds the node when it is in range and descends only into the sides that can still hold values in range.

How to solve Range Sum of BST

A plain traversal sums the in-range values; the search-tree order lets it skip every subtree that lies entirely below low or above high.

Approach

1. Push the root onto a stack and keep a running total.
2. Pop a node. If low <= val <= high, add val to total.
3. Descend left only if val > low (smaller values may still be in range), and right only if val < high.
4. When the stack is empty, return total.

Why it works

Every value in a left subtree is smaller than its node, so when val <= low the whole left subtree is below the range; symmetrically for the right subtree when val >= high. No skipped node could have contributed.

Complexity

• Time — O(n) worst case, O(h + k) when only k nodes fall in the range
• Space — O(h) for the stack

Pitfalls

• The range is inclusive at both ends.
• The sum fits in 32 bits under these limits (at most 2·10^4 distinct values up to 10^5 add up to under 1.9·10^9).

Reference solution

Python

from typing import Optional

def rangeSumBST(root: Optional[TreeNode], low: int, high: int) -> int:
    total = 0
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        if low <= node.val <= high:
            total += node.val
        if node.left and node.val > low:
            stack.append(node.left)
        if node.right and node.val < high:
            stack.append(node.right)
    return total

Java

public static int rangeSumBST(TreeNode root, int low, int high) {
    int total = 0;
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node.val >= low && node.val <= high) total += node.val;
        if (node.left != null && node.val > low) stack.push(node.left);
        if (node.right != null && node.val < high) stack.push(node.right);
    }
    return total;
}

C++

int rangeSumBST(TreeNode* root, int low, int high) {
    int total = 0;
    vector<TreeNode*> stack;
    if (root) stack.push_back(root);
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        if (node->val >= low && node->val <= high) total += node->val;
        if (node->left && node->val > low) stack.push_back(node->left);
        if (node->right && node->val < high) stack.push_back(node->right);
    }
    return total;
}

JavaScript

var rangeSumBST = function(root, low, high) {
    var total = 0, stack = root === null ? [] : [root];
    while (stack.length > 0) {
        var node = stack.pop();
        if (node.val >= low && node.val <= high) total += node.val;
        if (node.left !== null && node.val > low) stack.push(node.left);
        if (node.right !== null && node.val < high) stack.push(node.right);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy