Exploring the Hidden Treasure: 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

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

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

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++

1struct TreeNode {
2    int val;
3    TreeNode *left;
4    TreeNode *right;
5    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6};
7
8int rangeSumBST(TreeNode* root, int low, int high) {
9    if (!root) return 0;
10    int total = 0;
11    if (low <= root->val && root->val <= high) {
12        total += root->val;
13    }
14    // Recurse: Account for all possibilities by summing the values from the nodes
15    total += rangeSumBST(root->left, low, high);
16    total += rangeSumBST(root->right, low, high);
17    return total;
18}

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

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