LeetCode Solution: 938. Range Sum of BST

#leetcode #dsa #programming #tutorial

Unleash Your Inner Tree Wizard: Summing Values in a BST Range (LeetCode #938)

Hey fellow coders! 👋 Vansh2710 here, diving deep into another LeetCode adventure. Today, we're tackling a super common and insightful problem that truly highlights the power of Binary Search Trees (BSTs): Problem 938: Range Sum of BST.

This problem is a fantastic way to solidify your understanding of tree traversals and how to leverage the unique properties of a BST for efficiency. Let's get cracking!

🌳 Problem Explanation: What's the Goal?

Imagine you have a special kind of tree called a Binary Search Tree (BST). What makes it special? For every node in the tree:

All values in its left subtree are smaller than the node's own value.
All values in its right subtree are larger than the node's own value.

Pretty neat, right? This property is what makes BSTs so powerful for searching and sorting.

Now, for this problem, you're given:

The root node of one of these amazing BSTs.
Two integers, low and high.

Your mission, should you choose to accept it (which you will!): Find the sum of all node values that fall within the inclusive range [low, high]. This means any node with a value val where low <= val <= high should be added to our total.

Let's look at an example to make it crystal clear:

Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

Here's how that tree looks and why the answer is 32:

        10
       /  \
      5    15
     / \    \
    3   7    18

Nodes in range [7, 15]:

7 (Yes, 7 is >= 7 and <= 15)
10 (Yes, 10 is >= 7 and <= 15)
15 (Yes, 15 is >= 7 and <= 15)

The sum is 7 + 10 + 15 = 32. Nodes like 3, 5, and 18 are outside the range, so we ignore them.

🤔 Intuition: The "Aha!" Moment

At first glance, you might think, "Okay, I'll just traverse the entire tree (like a depth-first search or breadth-first search), check each node, and if it's in the range, add it to my sum." And you know what? That approach would work! It's perfectly valid.

But wait, we have a Binary Search Tree! Can we do better? The BST property is our secret weapon here. It tells us a lot about which parts of the tree are worth exploring and which are definitely not.

Here's the "aha!":

If our current node's value (root->val) is smaller than low, we know for sure that its entire left subtree contains values even smaller than root->val. So, none of them can possibly be in our [low, high] range. We can completely skip the left subtree and only look at the right subtree!
Similarly, if root->val is larger than high, we know its entire right subtree contains values even larger than root->val. None of those can be in our range. We can skip the right subtree and only look at the left subtree!
If root->val is within our [low, high] range, then we add it to our sum, AND we need to explore both its left and right subtrees, because they might contain other nodes within the range.

This insight allows us to "prune" (cut off) entire branches of the tree that we know won't contain any relevant nodes, making our solution much more efficient!

🚀 Approach: A Recursive Journey

We'll use a recursive Depth-First Search (DFS) approach to traverse the tree, smartly skipping subtrees based on the BST property.

Here's the step-by-step logic:

Base Case: If we encounter a null node (meaning we've gone past a leaf or an empty branch), there's nothing to add. We simply return 0. This stops our recursion.
Check Current Node's Value:
- If root->val is between low and high (inclusive):
  - This node's value is part of our sum! Add root->val to our total.
  - Since its children could also be in the range, we need to recursively call our function for both the root->left and root->right subtrees and add their returned sums.
  - So, return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);

*   **If `root->val` is less than `low`:**
    *   We know `root->val` is too small.
    *   Because it's a BST, all values in its `root->left` subtree will be even *smaller* than `root->val`, so they definitely won't be in our `[low, high]` range. We can ignore the left subtree!
    *   However, values in the `root->right` subtree *could* be larger than `low` and thus potentially in our range.
    *   So, we only need to recursively call for the `root->right` subtree: `return rangeSumBST(root->right, low, high);`

*   **If `root->val` is greater than `high`:**
    *   We know `root->val` is too large.
    *   Because it's a BST, all values in its `root->right` subtree will be even *larger* than `root->val`, so they definitely won't be in our `[low, high]` range. We can ignore the right subtree!
    *   However, values in the `root->left` subtree *could* be smaller than `high` and thus potentially in our range.
    *   So, we only need to recursively call for the `root->left` subtree: `return rangeSumBST(root->left, low, high);`

And that's it! This intelligent pruning makes our solution incredibly efficient.

🧑‍💻 Code

Here's the C++ implementation reflecting our approach:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        // Base case: If the current node is null, there's nothing to add.
        if (root == nullptr) {
            return 0;
        }

        // Case 1: Current node's value is within the range [low, high]
        if (root->val >= low && root->val <= high) {
            // Add current node's value and recursively sum from both children.
            // Both left and right subtrees might contain nodes in the range.
            return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
        }
        // Case 2: Current node's value is less than 'low'
        else if (root->val < low) {
            // All nodes in the left subtree will also be less than 'low' (BST property).
            // So, we only need to explore the right subtree.
            return rangeSumBST(root->right, low, high);
        }
        // Case 3: Current node's value is greater than 'high'
        else { // root->val > high
            // All nodes in the right subtree will also be greater than 'high' (BST property).
            // So, we only need to explore the left subtree.
            return rangeSumBST(root->left, low, high);
        }
    }
};

⏱️ Complexity Analysis

Let's break down how efficient our solution is:

Time Complexity: O(N) in the worst case, but often much better.
- In the worst-case scenario (e.g., if low is 1 and high is 10^5, covering the entire tree's possible range), we might end up visiting every single node in the tree. If there are N nodes, this would be O(N).
- However, thanks to the BST property and our pruning strategy, we only visit nodes that could potentially be within the [low, high] range. This means we avoid traversing entire subtrees that we know are irrelevant. So, while the upper bound is O(N), for many inputs, it's significantly faster than a generic tree traversal.
Space Complexity: O(H)
- This is due to the recursion call stack. H represents the height of the binary search tree.
- In the worst case (a skewed tree, resembling a linked list), the height H could be N (the number of nodes). So, space complexity would be O(N).
- In the best/average case (a balanced tree), the height H is log N. So, space complexity would be O(log N).

💡 Key Takeaways

BST Properties are Gold: Always look for ways to leverage the unique characteristics of a data structure. For BSTs, the left < root < right rule is incredibly powerful for optimizing searches and traversals.
Recursive Thinking for Trees: Many tree problems lend themselves beautifully to recursive solutions. Define your base case and how to combine results from subproblems.
Pruning for Performance: Smartly skipping irrelevant parts of the data structure (like entire subtrees here) can drastically improve the efficiency of your algorithms.

This problem is a fantastic stepping stone for understanding more complex BST problems and reinforcing your tree traversal skills. Keep practicing, and you'll be a tree wizard in no time! Happy coding! ✨

Author Account: Vansh2710 | Time Published: 2026-04-04 22:44:40