Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Approach 1: Recursive:

class Solution {
    int sum;
    public int rangeSumBST(TreeNode root, int low, int high) {
        sum =0;
        dfs(root, low, high);    
        return sum;
    }
    
    public void dfs(TreeNode node, int low, int high){
        if(node != null){
            if(low <= node.val && node.val <= high){
                sum +=node.val;
            }
            
            if(low < node.val){
                dfs(node.left, low, high);
            }
            
            if(node.val < high){
                dfs(node.right, low, high);
            }
        }
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

Approach 2: Iterative:

class Solution {

    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        Stack stack = new Stack<>();
        stack.push(root);
        
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node != null){
                if(low <= node.val && node.val <= high){
                    sum +=node.val;
                }

                if(low < node.val){
                    stack.push(node.left);
                }

                if(node.val < high){
                    stack.push(node.right);
                }
            }
        }
        return sum;
    }
    
}

Time Complexity: O(n) and Space Complexity: O(n)

The "Range Sum of BST" problem involves calculating the sum of all nodes within a binary search tree (BST) that lie within a specified range [low, high]. This problem is a good example of how the properties of a BST can be leveraged to efficiently find and sum up values within a range, without needing to visit all the nodes.

In a BST, for each node: - All values in the left subtree are smaller. - All values in the right subtree are larger.

Using these properties, we can efficiently traverse the tree and calculate the sum of the nodes within the given range.

Problem Statement

Given the root of a binary search tree and two integers low and high, return the sum of all the values of the nodes with a value in the inclusive range [low, high].

The tree node structure is given above. The task is to compute the sum of all nodes whose values are in the range [low, high].

Approach

To efficiently solve the problem, we can perform a depth-first search (DFS) traversal of the tree. By utilizing the properties of the BST, we can prune the search and avoid traversing unnecessary nodes:

• If the current node's value is less than low, we know that all values in the left subtree will also be smaller than low, so we can skip the left subtree.
• If the current node's value is greater than high, we know that all values in the right subtree will also be greater than high, so we can skip the right subtree.
• If the current node's value is within the range [low, high], we include its value in the sum and recursively explore both the left and right subtrees.

This approach allows us to avoid unnecessary traversals, improving efficiency compared to a brute force approach that visits all nodes.

Algorithm

The algorithm follows these steps:

1. If the root is None, return 0.
2. If the node's value is less than the low value, recursively calculate the sum in the right subtree.
3. If the node's value is greater than the high value, recursively calculate the sum in the left subtree.
4. If the node's value is within the range, add the node's value to the sum and recursively calculate the sum of both the left and right subtrees.
5. Return the accumulated sum.

This approach ensures that only relevant nodes are visited, optimizing the time complexity.

Example

Consider the following Binary Search Tree:

               10
              /  \
             5   15
            / \    \
           3   7    18
        

If we want to compute the sum of the values within the range [7, 15], we would consider the nodes with values 7, 10, and 15. The sum of these values is 32.

Code Implementation

Below is the Python implementation of the algorithm to calculate the range sum of BST nodes within the given range [low, high]:

Time Complexity

The time complexity of this solution is O(h), where h is the height of the tree. In the worst case, we may have to visit every node in the tree. However, because we prune unnecessary subtrees, the number of nodes we visit is typically smaller, especially if the tree is balanced.

The space complexity is O(h) due to the recursion stack. In the worst case (an unbalanced tree), the height can be O(n), where n is the number of nodes in the tree. In the best case (a balanced tree), the height is O(log n).

Optimized Approach

The described solution is already quite efficient. The pruning of subtrees ensures that we don't waste time visiting irrelevant nodes. In cases where the tree is unbalanced, other techniques, such as balancing the tree or using self-balancing trees like AVL or Red-Black trees, can help ensure better performance. However, for the majority of cases, this approach is optimal.

Time Complexity (Optimized)

The time complexity remains O(h), where h is the height of the tree. In a balanced tree, this is O(log n), and in the worst case (an unbalanced tree), it can be O(n).

The space complexity remains O(h), where h is the height of the tree, as this is the maximum depth of the recursion stack.

Conclusion

The "Range Sum of BST" problem demonstrates an efficient way to compute the sum of nodes within a given range by leveraging the BST properties. By pruning unnecessary subtrees and recursively visiting only relevant nodes, the solution is both time and space-efficient. The time complexity is O(h), where h is the height of the tree, and the space complexity is O(h) due to the recursion stack.