Range Sum of BST

Difficulty: Easy | Acceptance: 87.60% | Paid: No Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

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

• Examples
• Constraints
• Depth-First Search (DFS)
• DFS with BST Pruning
• Breadth-First Search (BFS)

Examples

Example 1:

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

Constraints

- The number of nodes in the tree is in the range [1, 2 * 10^4].
- 1 <= Node.val <= 10^5
- 1 <= low <= high <= 10^5
- All Node.val are unique.

Depth-First Search (DFS)

Intuition We perform a standard recursive traversal of the tree (pre-order, in-order, or post-order all work). We visit every node in the tree, check if its value falls within the range [low, high], and add it to our running total if it does.

Steps

• If the current node is null, return 0.
• Initialize a variable currentSum to 0.
• If the current node’s value is between low and high (inclusive), add the value to currentSum.
• Recursively call the function on the left child and add the result to currentSum.
• Recursively call the function on the right child and add the result to currentSum.
• Return currentSum.

# 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
        
        total = 0
        if low <= root.val <= high:
            total += root.val
            
        total += self.rangeSumBST(root.left, low, high)
        total += self.rangeSumBST(root.right, low, high)
        
        return total

Complexity

• Time: O(N) where N is the number of nodes in the tree. We visit every node exactly once.
• Space: O(H) where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N. In the best case (balanced tree), H = log N.
• Notes: This approach is simple but does not take advantage of the BST property to skip subtrees.

DFS with BST Pruning

Intuition Since the tree is a Binary Search Tree (BST), we know that for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. We can use this property to prune (skip) entire branches of the tree that cannot possibly contain values within the [low, high] range.

Steps

• If the current node is null, return 0.
• If the current node’s value is less than low, we know the entire left subtree is also less than low. We skip the left recursion and only recurse on the right child.
• If the current node’s value is greater than high, we know the entire right subtree is greater than high. We skip the right recursion and only recurse on the left child.
• If the current node’s value is within the range, we add it to the sum and recurse on both children.

# 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 < low:
            # Current node and left subtree are too small, only check right
            return self.rangeSumBST(root.right, low, high)
        
        if root.val > high:
            # Current node and right subtree are too large, only check left
            return self.rangeSumBST(root.left, low, high)
        
        # Current node is in range, sum it and check both children
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

Complexity

• Time: O(N) in the worst case, but often much better. If the range is small, we skip large portions of the tree.
• Space: O(H) for the recursion stack.
• Notes: This is the optimal approach for BSTs as it leverages the sorted property to minimize work.

Breadth-First Search (BFS)

Intuition We can solve this iteratively using a queue. We process nodes level by level. Similar to the optimized DFS, we apply the BST pruning logic when deciding which children to add to the queue.

Steps

• Initialize a sum variable to 0 and a queue containing the root.
• While the queue is not empty:
  • Dequeue a node.
  • If the node’s value is within the range, add it to sum.
  • If the node’s value is greater than low, add the left child to the queue (if it exists).
  • If the node’s value is less than high, add the right child to the queue (if it exists).
• Return 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
from collections import deque

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0
        
        total = 0
        q = deque([root])
        
        while q:
            node = q.popleft()
            
            if low <= node.val <= high:
                total += node.val
            
            if node.left and node.val > low:
                q.append(node.left)
            
            if node.right and node.val < high:
                q.append(node.right)
                
        return total

Complexity

• Time: O(N) in the worst case.
• Space: O(N) for the queue in the worst case (e.g., when the tree is a complete binary tree, the last level can hold up to N/2 nodes).
• Notes: Useful for avoiding recursion stack overflow on extremely deep trees, though generally uses more memory than DFS for balanced trees.