938. Range Sum of BST - Explanation

Description

You are 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 = [5,3,8,1,4,7,9,null,2], low = 3, high = 8

Output: 27

Explanation: Nodes 5, 3, 8, 4 and 7 are in the range [3, 8]. 5 + 3 + 8 + 4 + 7 = 27.

Example 2:

Input: root = [4,3,5,2,null], low = 2, high = 4

Output: 9

Explanation: Nodes 4, 3, and 2 are in the range [2, 4]. 4 + 3 + 2 = 9.

Constraints:

1 <= The number of nodes in the tree <= 20,000.
1 <= Node.val, low, high <= 100,000
All Node.val are unique.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search Tree (BST) Properties - Understanding that left subtree values are smaller and right subtree values are larger than the current node
Depth First Search (DFS) - Recursive tree traversal to visit all nodes and accumulate values
Tree Pruning - Using BST ordering to skip entire subtrees that cannot contain values in the target range

1. Depth First Search

Intuition

We traverse the entire tree and sum up values that fall within the given range. For each node, we check if its value is between low and high, adding it to our sum if so. We then recursively process both children. This approach visits every node regardless of the BST property.

Algorithm

Base case: if the node is null, return 0.
Check if the current node's value is within [low, high]. If yes, include it in the result.
Recursively compute the range sum for the left subtree.
Recursively compute the range sum for the right subtree.
Return the sum of all contributions.

# 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:
        if not root:
            return 0

        res = root.val if low <= root.val <= high else 0
        res += self.rangeSumBST(root.left, low, high)
        res += self.rangeSumBST(root.right, low, high)
        return res

/**
 * 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;
 *     }
 * }
 */
public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;

        int res = (low <= root.val && root.val <= high) ? root.val : 0;
        res += rangeSumBST(root.left, low, high);
        res += rangeSumBST(root.right, low, high);
        return res;
    }
}

/**
 * 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) return 0;

        int res = (low <= root->val && root->val <= high) ? root->val : 0;
        res += rangeSumBST(root->left, low, high);
        res += rangeSumBST(root->right, low, high);
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @param {number} low
     * @param {number} high
     * @return {number}
     */
    rangeSumBST(root, low, high) {
        if (!root) return 0;

        let res = low <= root.val && root.val <= high ? root.val : 0;
        res += this.rangeSumBST(root.left, low, high);
        res += this.rangeSumBST(root.right, low, high);
        return res;
    }
}

/**
 * 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) {
        if (root == null) return 0;

        int res = (root.val >= low && root.val <= high) ? root.val : 0;
        res += RangeSumBST(root.left, low, high);
        res += RangeSumBST(root.right, low, high);
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rangeSumBST(root *TreeNode, low int, high int) int {
    if root == nil {
        return 0
    }

    res := 0
    if root.Val >= low && root.Val <= high {
        res = root.Val
    }
    res += rangeSumBST(root.Left, low, high)
    res += rangeSumBST(root.Right, low, high)
    return res
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int {
        if (root == null) return 0

        var res = if (root.`val` in low..high) root.`val` else 0
        res += rangeSumBST(root.left, low, high)
        res += rangeSumBST(root.right, low, high)
        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        guard let root = root else { return 0 }

        var res = (root.val >= low && root.val <= high) ? root.val : 0
        res += rangeSumBST(root.left, low, high)
        res += rangeSumBST(root.right, low, high)
        return res
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }
impl Solution {
    pub fn range_sum_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                let node = node.borrow();
                let mut res = if node.val >= low && node.val <= high { node.val } else { 0 };
                res += Self::range_sum_bst(node.left.clone(), low, high);
                res += Self::range_sum_bst(node.right.clone(), low, high);
                res
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

2. Depth First Search (Optimal)

Intuition

We can leverage the BST property to prune unnecessary branches. If the current node's value is greater than high, all values in the right subtree are also too large, so we only need to search left. Similarly, if the current value is less than low, we only search right. This eliminates entire subtrees that cannot contribute to the sum.

Algorithm

Base case: if the node is null, return 0.
If the current value exceeds high, skip the right subtree and recurse only on the left.
If the current value is below low, skip the left subtree and recurse only on the right.
Otherwise, the current value is in range. Add it to the sum of both subtree results.
Return the computed sum.

# 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:
        if not root:
            return 0

        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)

        return (
            root.val +
            self.rangeSumBST(root.left, low, high) +
            self.rangeSumBST(root.right, low, high)
        )

/**
 * 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;
 *     }
 * }
 */
public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;

        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }

        return root.val + rangeSumBST(root.left, low, high) +
                          rangeSumBST(root.right, low, high);
    }
}

/**
 * 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) return 0;

        if (root->val > high) {
            return rangeSumBST(root->left, low, high);
        }
        if (root->val < low) {
            return rangeSumBST(root->right, low, high);
        }

        return root->val + rangeSumBST(root->left, low, high) +
                           rangeSumBST(root->right, low, high);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @param {number} low
     * @param {number} high
     * @return {number}
     */
    rangeSumBST(root, low, high) {
        if (!root) return 0;

        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }

        return (
            root.val +
            this.rangeSumBST(root.left, low, high) +
            this.rangeSumBST(root.right, low, high)
        );
    }
}

/**
 * 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) {
        if (root == null) return 0;

        if (root.val > high) {
            return RangeSumBST(root.left, low, high);
        }
        if (root.val < low) {
            return RangeSumBST(root.right, low, high);
        }

        return root.val
             + RangeSumBST(root.left, low, high)
             + RangeSumBST(root.right, low, high);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rangeSumBST(root *TreeNode, low int, high int) int {
    if root == nil {
        return 0
    }

    if root.Val > high {
        return rangeSumBST(root.Left, low, high)
    }
    if root.Val < low {
        return rangeSumBST(root.Right, low, high)
    }

    return root.Val + rangeSumBST(root.Left, low, high) + rangeSumBST(root.Right, low, high)
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int {
        if (root == null) return 0

        if (root.`val` > high) {
            return rangeSumBST(root.left, low, high)
        }
        if (root.`val` < low) {
            return rangeSumBST(root.right, low, high)
        }

        return root.`val` + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        guard let root = root else { return 0 }

        if root.val > high {
            return rangeSumBST(root.left, low, high)
        }
        if root.val < low {
            return rangeSumBST(root.right, low, high)
        }

        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)
    }
}

impl Solution {
    pub fn range_sum_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                let node = node.borrow();
                if node.val > high {
                    return Self::range_sum_bst(node.left.clone(), low, high);
                }
                if node.val < low {
                    return Self::range_sum_bst(node.right.clone(), low, high);
                }
                node.val
                    + Self::range_sum_bst(node.left.clone(), low, high)
                    + Self::range_sum_bst(node.right.clone(), low, high)
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Iterative DFS

Intuition

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.

Algorithm

Initialize a stack with the root node and a result variable set to 0.
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.
Return the accumulated result.

# 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

/**
 * 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;
 *     }
 * }
 */
public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int res = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) 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;
    }
}

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

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @param {number} low
     * @param {number} high
     * @return {number}
     */
    rangeSumBST(root, low, high) {
        let res = 0;
        let stack = [root];

        while (stack.length > 0) {
            let node = 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;
    }
}

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

        while (stack.Count > 0) {
            var node = stack.Pop();
            if (node == null) continue;

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

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rangeSumBST(root *TreeNode, low int, high int) int {
    stack := []*TreeNode{root}
    res := 0

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if node == nil {
            continue
        }

        if node.Val >= low && node.Val <= high {
            res += node.Val
        }
        if node.Val > low {
            stack = append(stack, node.Left)
        }
        if node.Val < high {
            stack = append(stack, node.Right)
        }
    }

    return res
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int {
        val stack = ArrayDeque<TreeNode?>()
        stack.addLast(root)
        var res = 0

        while (stack.isNotEmpty()) {
            val node = stack.removeLast() ?: continue

            if (node.`val` in low..high) {
                res += node.`val`
            }
            if (node.`val` > low) {
                stack.addLast(node.left)
            }
            if (node.`val` < high) {
                stack.addLast(node.right)
            }
        }

        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        var stack: [TreeNode?] = [root]
        var res = 0

        while !stack.isEmpty {
            guard let node = stack.removeLast() else { continue }

            if node.val >= 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
    }
}

impl Solution {
    pub fn range_sum_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> i32 {
        let mut stack = vec![root];
        let mut res = 0;

        while let Some(opt) = stack.pop() {
            if let Some(node) = opt {
                let node = node.borrow();
                if node.val >= low && node.val <= high {
                    res += node.val;
                }
                if node.val > low {
                    stack.push(node.left.clone());
                }
                if node.val < high {
                    stack.push(node.right.clone());
                }
            }
        }

        res
    }
}

Time & Space Complexity

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

Common Pitfalls

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.