Range Sum of BST easy

Problem Statement

Given the root node of a binary search tree (BST) 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

Steps

1. Recursive Approach: We'll use a recursive function to traverse the BST.
2. Base Case: If the current node is None, return 0 (no sum).
3. Check Range: If the current node's value is within the [low, high] range, add its value to the sum.
4. Recursive Calls: Recursively call the function for the left and right subtrees, only if necessary. If the current node's value is less than low, we only need to explore the right subtree (since the BST is ordered). If the current node's value is greater than high, we only need to explore the left subtree. Otherwise, explore both subtrees.
5. Return Sum: Return the total sum.

Explanation

The solution leverages the properties of a Binary Search Tree. Because the BST is ordered, we can prune our search significantly. If a node's value is less than low, we know that all nodes in its left subtree will also be less than low, so we don't need to traverse them. Similarly, if a node's value is greater than high, we don't need to traverse its right subtree. This pruning makes the algorithm much more efficient than a brute-force approach that would traverse the entire tree.

Code

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):
    """
    :type root: TreeNode
    :type low: int
    :type high: int
    :rtype: int
    """
    total_sum = 0

    def dfs(node):
        nonlocal total_sum  #Allows modification of outer scope variable
        if not node:
            return
        
        if low <= node.val <= high:
            total_sum += node.val

        if node.val > low:
            dfs(node.left)
        if node.val < high:
            dfs(node.right)

    dfs(root)
    return total_sum


# Example usage:
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)

low = 7
high = 15
result = rangeSumBST(root, low, high)
print(f"Sum of nodes in range [{low}, {high}]: {result}") # Output: 32

root2 = TreeNode(10)
root2.left = TreeNode(5)
root2.right = TreeNode(15)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(7)
root2.right.left = TreeNode(13)
root2.right.right = TreeNode(18)
root2.left.left.left = TreeNode(1)
root2.left.right.right = TreeNode(6)

low2 = 6
high2 = 10
result2 = rangeSumBST(root2, low2, high2)
print(f"Sum of nodes in range [{low2}, {high2}]: {result2}") # Output: 23

Complexity

• Time Complexity: O(N) in the worst case, where N is the number of nodes in the BST. However, in the best case (where low and high are such that a large portion of the tree can be pruned), the time complexity will be much less than O(N).
• Space Complexity: O(H) in the worst case, where H is the height of the BST. This is due to the recursive call stack. In a balanced BST, H = log N, and in a skewed BST, H = N.