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
 Base Case: If the root is null, return 0 as there is no node to explore.
 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.  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.  InRange: 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.  Recursive Calls: Make recursive calls accordingly to the above three conditions.
 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
