Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        elif root.val > high:
            return self.rangeSumBST(root.left, low, high)
        else:
            return (root.val +
                    self.rangeSumBST(root.left, low, high) +
                    self.rangeSumBST(root.right, low, high))
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        if (root->val < low)
            return rangeSumBST(root->right, low, high);
        else if (root->val > high)
            return rangeSumBST(root->left, low, high);
        else
            return root->val +
                rangeSumBST(root->left, low, high) +
                rangeSumBST(root->right, low, high);
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val < low)
            return rangeSumBST(root.right, low, high);
        else if (root.val > high)
            return rangeSumBST(root.left, low, high);
        else
            return root.val +
                rangeSumBST(root.left, low, high) +
                rangeSumBST(root.right, low, high);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var rangeSumBST = function(root, low, high) {
    if (!root) return 0;
    if (root.val < low)
        return rangeSumBST(root.right, low, high);
    else if (root.val > high)
        return rangeSumBST(root.left, low, high);
    else
        return root.val +
            rangeSumBST(root.left, low, high) +
            rangeSumBST(root.right, low, high);
};
      

Problem Description

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].

The BST property means for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

• You must consider every node whose value falls within the range.
• There is exactly one valid solution for each input.
• Do not reuse or double-count any node's value.

The input consists of the root node of the BST and the integers low and high.

Thought Process

To solve this problem, our first instinct might be to traverse every node in the tree and check if its value falls within the range [low, high]. If it does, we add it to our sum. This brute-force approach works, but it does not take advantage of the BST structure.

Since a BST organizes values in a sorted manner, we can skip entire branches that cannot possibly contain values within our target range. For example, if the current node's value is less than low, then all values in its left subtree will also be less than low and can be ignored. This insight allows us to optimize our traversal and avoid unnecessary work.

The main trick is to traverse the tree recursively, but at each node, decide whether to continue with both children, only one, or none, based on the current node's value.

Solution Approach

• Step 1: Start at the root node.
• Step 2: For each node:
  • If the node is null, return 0 (base case for recursion).
  • If the node's value is less than low, only search the right subtree (since all left values are even smaller).
  • If the node's value is greater than high, only search the left subtree (since all right values are even larger).
  • If the node's value is within [low, high], include it in the sum and search both subtrees.
• Step 3: Recursively apply this logic to the left and right children as appropriate.
• Step 4: Return the accumulated sum.

This approach is efficient because it prunes entire subtrees that cannot possibly have values in the desired range, thanks to the BST property.

Example Walkthrough

Example: Suppose the BST is:

        10
       /  \
      5   15
     / \    \
    3   7    18
  

Let low = 7 and high = 15.

1. Start at node 10. 10 is in [7, 15], so add 10 to sum.
2. Go left to node 5. 5 is less than 7, so only search the right subtree (node 7).
3. At node 7, 7 is in [7, 15], so add 7 to sum. Its children are null, so return.
4. Go right from root to node 15. 15 is in [7, 15], so add 15 to sum. Its right child is 18, which is greater than 15, so we only check the left (which is null).
5. Sum = 10 + 7 + 15 = 32.

Notice how we never visited node 3 or node 18's right subtree, as they cannot be within the range.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N), where N is the number of nodes. Every node is visited.
  • Space Complexity: O(H), where H is the height of the tree (due to recursion stack).
• Optimized BST approach (current solution):
  • Time Complexity: O(M), where M is the number of nodes visited. In the best case, we skip large parts of the tree, so M < N.
  • Space Complexity: O(H), as before, due to recursion stack.

The pruning based on BST property can greatly reduce the number of nodes we process, especially if the range is small compared to the whole tree.

Summary

By leveraging the BST property, we avoid unnecessary traversal, making our solution efficient. The key insight is to prune subtrees that cannot possibly contain values in the target range. This reduces both time and computational resources, resulting in an elegant and optimal solution for the Range Sum of BST problem.