Range Sum of BST

Easy · Graphs · Explanation and code example

Iterative DFS

How it works

The recursive solution can be converted to an iterative one using an explicit stack. We maintain the same pruning logic: only push children onto the stack if they might contain values in range. This avoids function call overhead while preserving the efficiency of the optimal approach.

Steps

  1. Initialize a stack with the root node and a result variable set to 0.
  2. While the stack is not empty:
    • Pop a node. If null, continue.
    • If the node's value is in range [low, high], add it to the result.
    • If the node's value is greater than low, push the left child.
    • If the node's value is less than high, push the right child.
  3. Return the accumulated result.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Not Leveraging BST Property for Pruning

Treating the tree as a regular binary tree and visiting every node wastes time. Since it is a BST, when the current node's value exceeds high, the entire right subtree contains only larger values and can be skipped. Similarly, when the value is below low, the left subtree can be skipped. Failing to prune these branches results in O(n) time even when only a small portion of nodes fall within the range.

Incorrect Range Boundary Checks

Using strict inequalities (< and >) instead of inclusive checks (<= and >=) when determining whether to include the current node's value causes off-by-one errors. The condition should be low <= node.val <= high to include boundary values. Missing boundary values leads to incorrect sums when low or high exactly match node values in the tree.

Python code example

from typing import Optional

# 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: Optional[TreeNode], low: int, high: int) -> int:
        stack = [root]
        res = 0

        while stack:
            node = stack.pop()
            if not node:
                continue

            if low <= node.val <= high:
                res += node.val
            if node.val > low:
                stack.append(node.left)
            if node.val < high:
                stack.append(node.right)

        return res

C++ code example

/**
 * 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) {
        int res = 0;
        stack<TreeNode*> stack;
        stack.push(root);

        while (!stack.empty()) {
            TreeNode* node = stack.top();
            stack.pop();
            if (!node) continue;

            if (low <= node->val && node->val <= high) {
                res += node->val;
            }
            if (node->val > low) {
                stack.push(node->left);
            }
            if (node->val < high) {
                stack.push(node->right);
            }
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations