Hide sidebar
leetcode/DSA courseSystem Design

Range Sum of BST

TreesDFS
EasyLeetCode #938

Problem Statement

Given the `root` 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

105371518

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

Output: 32

Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Algorithm Explanation

We can solve this problem efficiently by leveraging the properties of a Binary Search Tree (BST). We'll perform a DFS traversal, but we can prune branches that are out of the given range.

Algorithm Steps

  • DFS Traversal: We'll use a recursive DFS function that takes a node as input.
  • Node in Range: If the current node's value is within the `[low, high]` range, we add its value to our running sum and recursively call on both its left and right children.
  • Node too Low: If the current node's value is less than `low`, we know that all nodes in its left subtree will also be too low, so we only need to recursively call on its right child.
  • Node too High: If the current node's value is greater than `high`, we know that all nodes in its right subtree will also be too high, so we only need to recursively call on its left child.
105371518
Start
Starting DFS from the root.
Total Sum: 0
Range Sum of BST Solution

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        # Base case: if the root is null, return 0
        if not root:
            return 0
        
        ans = 0
        # If the node's value is in the range, add it to the sum
        if low <= root.val <= high:
            ans += root.val
        
        # If the current node's value is greater than low, there might be relevant nodes in the left subtree
        if root.val > low:
            ans += self.rangeSumBST(root.left, low, high)
        
        # If the current node's value is less than high, there might be relevant nodes in the right subtree
        if root.val < high:
            ans += self.rangeSumBST(root.right, low, high)
            
        return ans