Range Sum of BST — LeetCode 938 BST Pruning DFS

Problem Statement#

Given the root of a Binary Search Tree and integers low and high, return the sum of values of all nodes with values in the inclusive range [low, high].

Constraints:

• Number of nodes is in the range [1, 2 * 10^4].
• 1 <= Node.val <= 10^5.
• 1 <= low <= high <= 10^5.

Input:  root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32  // 7 + 10 + 15

Input:  root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23  // 6 + 7 + 10

Why This Problem Matters#

LeetCode 938 — Range Sum of BST is the most popular "prune the BST" question. Amazon, Facebook (Meta), Google, and Apple use it as a fast 5-minute opener. Bloomberg and Twitter also use it for SQL-engine interviews because range queries map directly to indexed BTrees.

The lesson is simple: if the input is a BST, do not walk every node. Use the BST property to skip entire subtrees that cannot contain any in-range value. That is the difference between a BST solution and a "binary tree that happens to be sorted" solution.

This is also a natural lead-in to BST iterators (LC 173), Closest BST Value, Trim a BST (LC 669), and any range-query problem.

The Core Insight#

At each node:

• If node.val < low, the entire left subtree is below low — skip it, recurse right only.
• If node.val > high, the entire right subtree is above high — skip it, recurse left only.
• Otherwise the value is in range, add it, recurse both ways.

This pruning pulls the runtime from O(n) down to O(h + k) where k is the number of in-range nodes.

Visual Dry Run#

Tree [10, 5, 15, 3, 7, null, 18], low = 7, high = 15:

Final sum 32.

Solution (Optimal)#

# Python — pruned recursive DFS using BST property
class Solution:
    def rangeSumBST(self, root, low, high):
        if not root:
            return 0
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        if root.val > high:
            return self.rangeSumBST(root.left,  low, high)
        return (root.val
                + self.rangeSumBST(root.left,  low, high)
                + self.rangeSumBST(root.right, low, high))

// JavaScript — pruned DFS
var rangeSumBST = function(root, low, high) {
    if (!root) return 0;
    if (root.val < low)  return rangeSumBST(root.right, low, high);
    if (root.val > high) return rangeSumBST(root.left,  low, high);
    return root.val
        + rangeSumBST(root.left,  low, high)
        + rangeSumBST(root.right, low, high);
};

# Iterative pruning using a stack
class Solution:
    def rangeSumBST(self, root, low, high):
        total, stack = 0, [root]
        while stack:
            n = stack.pop()
            if not n: continue
            if n.val < low:
                stack.append(n.right)
            elif n.val > high:
                stack.append(n.left)
            else:
                total += n.val
                stack.append(n.left)
                stack.append(n.right)
        return total

Time: O(h + k) where k is the number of in-range nodes and h is the tree height. Space: O(h) recursion or stack.

Common Mistakes#

• Treating the tree as a generic binary tree and walking all n nodes — passes but flagged for not using BST.
• Off-by-one when comparing — the range is inclusive on both ends; use < and >, not <= and >=.
• Forgetting to recurse the right subtree when the current value is below low.
• Adding node.val before checking the range — easy to introduce when refactoring.

Interview Tips#

• Lead with "the input is a BST so we can prune". That single sentence shifts the conversation.
• State the time complexity in terms of h and the size of the answer set, not n.
• Mention iterative version if interviewer asks about deep skewed trees.
• Bring up Trim a BST as a closely related "transform" version.

Follow-up Questions#

• Trim a BST (LC 669)? Same pruning logic but reconnect the kept subtrees and return the new root.
• BST Iterator (LC 173)? Inorder iterator with next / hasNext that you can use with a range filter.
• Range count? Same algorithm, replace += val with += 1.
• Persistent / immutable BST? Allocate new nodes during pruning to keep the original.
• Range sum on a regular binary tree? Cannot prune — must walk all n nodes.

Key Takeaways#

• LeetCode 938 Range Sum of BST runs in O(h + k) time and O(h) space using BST pruning.
• The pruning rule is val < low -> right only, val > high -> left only, otherwise add and recurse both.
• Asked at Amazon, Facebook (Meta), Google, Apple, Bloomberg, Twitter for range queries.
• Foundation for Trim a BST (LC 669), BST Iterator (LC 173), Closest BST Value (LC 270/272).
• The same technique generalises to range count and range list operations on a BST.
• Iterative stack version handles deep skewed BSTs safely.
• Always say "BST property lets me prune" — it is the entire point of the question.