Range Sum of BST easy

Problem Statement

Given the root 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 null, return 0.
3. Check Range: If the current node's value is within the range [low, high], add its value to the sum.
4. Recursive Calls: Recursively call the function for the left and right subtrees, only if they could potentially contain nodes within the range. This pruning is crucial for efficiency.

Explanation

The solution leverages the property of Binary Search Trees. Since the BST is ordered, we can efficiently prune our search. If the current node's value is less than low, we only need to explore the right subtree (because values in the left subtree will be even smaller). Similarly, if the current node's value is greater than high, we only need to explore the left subtree. This pruning significantly reduces the number of nodes we need to visit, improving performance.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
    let sum = 0;

    function traverse(node: TreeNode | null): void {
        if (node === null) return;

        if (node.val >= low && node.val <= high) {
            sum += node.val;
        }

        if (node.val > low) { // Explore left subtree only if it could contain values within range
            traverse(node.left);
        }
        if (node.val < high) { // Explore right subtree only if it could contain values within range
            traverse(node.right);
        }
    }

    traverse(root);
    return sum;
};

Complexity

• Time Complexity: O(N) in the worst case, where N is the number of nodes in the BST. However, in practice, it's often much better than O(N) due to the pruning of subtrees. If the range is very narrow, or if the tree is well-balanced, it might approach O(log N) for the search.

• 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 would be log N, while in a skewed BST it could be N.