Range Sum of BST

You are required to find the sum of all nodes’ values within a specified range [low, high] in a Binary Search Tree (BST).

Approach

1. Base Case: If the root is null, return 0 as there is no node to explore.
2. Left Subtree: If the value of the current root node is less than low, we know that all the values in the left subtree will be less than low. So, we need to explore only the right subtree.
3. Right Subtree: Similarly, if the value of the current root node is greater than high, all the values in the right subtree will be greater than high. So, we need to explore only the left subtree.
4. In-Range: If the value of the current node is in the range [low, high], we include this value in our sum and explore both left and right subtrees.
5. Recursive Calls: Make recursive calls accordingly to the above three conditions.
6. Return the Sum: Return the sum of values of all nodes within the range.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0

        # If current node value is less than low, explore the right subtree
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)

        # If current node value is greater than high, explore the left subtree
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)

        # If current node value is in range, explore both subtrees and include current value
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

Example

• 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], so the sum is 7 + 10 + 15 = 32.

Insights

• Time Complexity: The time complexity is (O(n)), where (n) is the number of nodes in the tree. In the worst case, you may need to visit all the nodes.
• Space Complexity: The space complexity is (O(h)), where (h) is the height of the tree. This accounts for the recursive call stack in the case of a balanced tree. In the worst case (a skewed tree), the space complexity would be (O(n)).
• Utilizing BST Property: The solution efficiently utilizes the property of a BST, where all left children are less than the root and all right children are greater than the root, to eliminate unnecessary searches.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @param {Integer} low
# @param {Integer} high
# @return {Integer}

def range_sum_bst(root, low, high)
    count = 0

    if root.nil?
        return count
    end
    if root.val.between?(low, high)
        count += root.val
    end

    count += range_sum_bst(root.left, low, high)
    count += range_sum_bst(root.right, low, high)
    count
end