{x}
blog image

Range Sum of BST

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 = [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 * 104].
  • 1 <= Node.val <= 105
  • 1 <= low <= high <= 105
  • All Node.val are unique.

Solution Explanation: Range Sum of BST

This problem asks us to find the sum of all node values within a given range [low, high] in a Binary Search Tree (BST). The efficient approach leverages the properties of a BST to minimize the number of nodes visited.

Algorithm (Depth-First Search - DFS):

The core idea is to perform a depth-first traversal of the BST. For each node encountered, we check if its value falls within the specified range [low, high].

  1. Base Case: If the current node is null (empty), we return 0 (no contribution to the sum).

  2. Range Check: If the node's value is within the range [low, high], we add its value to the sum.

  3. Recursive Calls: Because it's a BST:

    • If the node's value is greater than low, there might be nodes within the range in its left subtree. We recursively call the function on the left subtree.
    • If the node's value is less than high, there might be nodes within the range in its right subtree. We recursively call the function on the right subtree.

  4. Return Value: The function returns the accumulated sum for the subtree rooted at the current node.

Time and Space Complexity:

  • Time Complexity: O(N) - In the worst case, we might have to visit all N nodes in the BST. However, because of the BST property, we significantly prune the search space compared to a brute-force approach on a general tree.

  • Space Complexity: O(H) - The space complexity is determined by the maximum depth (H) of the recursion stack during the DFS traversal. In a balanced BST, H is log(N), while in a skewed BST, H can be N. Therefore, the space complexity is O(H), where H is the height of the tree.

Code Implementation (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def rangeSumBST(root, low, high):
    def dfs(node):
        if not node:
            return 0
        
        sum_val = node.val if low <= node.val <= high else 0
        
        if node.val > low:
            sum_val += dfs(node.left)
        if node.val < high:
            sum_val += dfs(node.right)
            
        return sum_val
    return dfs(root)
 
# Example usage:
root = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(7)), TreeNode(15, TreeNode(13), TreeNode(18)))
low = 7
high = 15
result = rangeSumBST(root, low, high)  # Output: 32

The code in other languages (Java, C++, Go, TypeScript, C#) follows the same algorithmic approach; only the syntax changes. The core logic of DFS and the range check remains consistent across all implementations.