Range Sum of BST

The Hidden Treasure – Range Sum of BST

A Binary Search Tree (BST) is a special type of binary tree where each node's left subtree contains values smaller than the node, and the right subtree contains values larger. In this lesson, we will explore the "Range Sum of BST" problem. This involves finding the sum of all node values in a BST that lie within a given range [low, high].

For example, in a BST with values {10, 5, 15, 3, 7, null, 18}, and a range [7, 15], the sum of node values in this range is 7 + 10 + 15 = 32. This problem helps in understanding how to traverse a BST and selectively process nodes based on conditions.

The idea is simple:

• Use Depth-First Search (DFS) or recursion to traverse the BST.
• Only consider nodes that fall within the given range.
• Skip unnecessary nodes to save time and directly sum the required values.

This problem is common in coding interviews and teaches the importance of optimized tree traversal.

Steps to Solve the Range Sum of BST Problem

• Start at the root of the BST. Check if the root value falls within the range [low, high].
• Add the value to the sum if it is within the range. If the node's value is between low and high, include it in the sum.
• Traverse the left subtree. If the current node's value is greater than low, move to the left subtree since smaller values lie there.
• Traverse the right subtree. If the current node's value is less than high, move to the right subtree since larger values lie there.
• Return the total sum. Combine the sums from both subtrees and the current node to get the final result.

Logic Building for Range Sum of BST

Did it ever cross your mind how to extract specified data in an efficient way from a Binary Search Tree (BST)? Let's say we are provided with a BST containing a bunch of numbers and were tasked to find the sum of all the numbers between certain limits. How can this be done? Should we search every single node for that, or is there an efficient way? Explore with us on this journey as we traverse both the brute force and the optimal approaches to solve the "Range Sum of BST" challenge.

Leaving no stone unturned

The naïve approach upon the first encounter with the problem would be to consider each node, just like checking every spot on a treasure map regardless of the clue. In doing this, we would be aware that no potential value can be missed; however, is this an effective way?

First moves

Alright, let's start with the brute force approach, and then we will discuss the optimal approach:

Brute force in Python

1
2
3
4
5
6
7
8
9
10
def rangeSumBST(root, low, high):
    if not root:
        return 0
    total = 0
    # Add it if the current node is in the range
    if root.val <= high and root.val >= low:
        total += root.val
    total += rangeSumBST(root.left, low, high)
    total += rangeSumBST(root.right, low, high)
    return total

This is where we utilize recursion in each node so that it tests whether it lies within the low and high; if so, sum it.

Brute force in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int rangeSumBST(TreeNode root, int low, int high) {
    if (root == null) {
        return 0;
    }
    int total = 0;
    // Add the value of this node if it falls in the provided range
    if (root.val <= high && root.val >= low) {
        total += root.val;
    }
    // Walk recursively through every node to cover everything
    total += rangeSumBST(root.left, low, high);
    total += rangeSumBST(root.right, low, high);
    return total;
}

This is the Java method, which is the same as the one provided in Python, using a recursive approach to visit each node and collect values within the range.

Brute force in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int rangeSumBST(TreeNode* root, int low, int high) {
    if (!root) return 0;
    int total = 0;
    if (low <= root->val && root->val <= high) {
        total += root->val;
    }
    // Recurse: Account for all possibilities by summing the values from the nodes
    total += rangeSumBST(root->left, low, high);
    total += rangeSumBST(root->right, low, high);
    return total;
}

In C++, we do the same thing—make sure you check each and every node, then just add it if the criteria are met.

The way of least resistance

We come back to the more optimized way of using properties of BSTs after exploring all possible ways. Due to the structure of a BST, whereby, for a node, its left children have values less than it and its right children have values greater than it, we can completely discard whole sections that do not satisfy our criteria by range.

Optimal Solution in Python

1
2
3
4
5
6
7
8
9
10
def rangeSumBST(root, low, high):
    if not root:
        return 0
    # Skip unnecessary nodes by leveraging BST properties
    if root.val < low:
        return rangeSumBST(root.right, low, high)
    if root.val > high:
        return rangeSumBST(root.left, low, high)
    # Node is within range, explore both subtrees
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high)

This Python function makes the code efficient by not traversing sub-trees that do not contain any value that can be a part of the sum within the range.

Conclusion: The Hidden Treasure

The brute force and the optimal approach to the problem really do refine a map. This will make clearer paths toward the treasure. The journey not only helps us understand the "Range Sum of BST" but also sharpens our problem-solving ability, preparing us for tougher challenges in data structures.