Vansh Aggarwal

Posted on Apr 16

LeetCode Solution: 938. Range Sum of BST

#leetcode #dsa #programming #tutorial

Range Sum of BST: The Smart Way to Sum Nodes in LeetCode 938!

Hey amazing developers! 👋 Vansh here, diving into another LeetCode adventure. Today, we're tackling a classic tree problem that's perfect for beginners but also packed with a clever optimization trick: 938. Range Sum of BST.

Don't let "Binary Search Tree" scare you! We're going to break it down, understand the magic, and solve it efficiently. Get ready for some tree-mendous insights!

🌳 The Problem Explained: Finding Your Range in a Tree

Imagine you have a family tree, but instead of people, it's made of numbers! This special kind of number tree is called a Binary Search Tree (BST). What makes it special? It follows two super important rules:

Left is Less: For any node, all the numbers in its left branch (or "subtree") are smaller than the node's own number.
Right is Right (larger): For any node, all the numbers in its right branch (or "subtree") are larger than the node's own number.

See how organized it is? This property is our secret weapon!

Now, for the problem itself: You're given the root (the very top node) of one of these amazing BSTs, and two numbers: low and high. Your mission, should you choose to accept it (which you will!), is to:

Find all the nodes in the tree whose values are between low and high (inclusive).
Add up all those values.
Return the total sum!

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

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

This tree looks like this:

      10
     /  \
    5    15
   / \    \
  3   7    18

We need to find numbers between 7 and 15.

Is 10 in [7, 15]? Yes!
Is 5 in [7, 15]? No.
Is 15 in [7, 15]? Yes!
Is 3 in [7, 15]? No.
Is 7 in [7, 15]? Yes!
Is 18 in [7, 15]? No.

So, the nodes in range are 7, 10, and 15.
Their sum is 7 + 10 + 15 = 32. And that's our output! Simple, right?

🤔 The "Aha!" Moment: Don't Just Traverse, Prune!

Okay, so we need to visit nodes, check their values, and sum them up if they're in range. A basic approach would be to visit every single node in the tree (like a regular walk-through), check its value, and add it if it fits. This would definitely work!

But is it the smartest way? This is a Binary Search Tree, not just any old tree! The special BST rules are our superpower here.

The "aha!" moment is realizing that we don't need to visit every branch. We can be much more efficient!

If we're at a node and its value is smaller than low: We know for sure that its left child (and everything in its left subtree) will be even smaller. So, there's absolutely no point in looking left – we can completely ignore that entire branch! We only need to check its right child, as those values will be larger.
If we're at a node and its value is larger than high: We know its right child (and its right subtree) will be even larger. So, again, we can skip that entire right branch! We only need to check its left child, as those values will be smaller.

This clever trick of skipping entire sections of the tree is called pruning, and it's what makes this problem efficient and fun!

🪜 Our Smart Approach: Recursive Pruning

We'll use a Depth-First Search (DFS) approach, which is a fancy way of saying we'll explore as far as possible down each branch before backtracking. Since trees are naturally recursive structures, a recursive DFS is a perfect fit here!

Here's our step-by-step game plan:

Initialize a total_sum: This variable will keep track of the sum of all nodes that fall within our [low, high] range. Start it at 0.
Define a dfs(node) helper function: This function will be called repeatedly to visit each node.
- Base Case: If node is None (meaning we've gone past a leaf node or encountered an empty branch), we simply stop and return. There's nothing to add.
- Check Current Node: If the current node.val is between low and high (inclusive), then hurray! We add node.val to our total_sum.
- Decide Where to Go Next (The Pruning Part!):
  - Should we go Left? We only need to explore the left subtree if there's a chance to find values greater than or equal to low. This means if node.val itself is greater than low, we might find low or values just above it in the left subtree. So, if node.val > low, we call dfs(node.left).
  - Should we go Right? Similarly, we only explore the right subtree if there's a chance to find values less than or equal to high. This means if node.val itself is less than high, we might find high or values just below it in the right subtree. So, if node.val < high, we call dfs(node.right).
Start the recursion: Call dfs(root) to kick off the process from the very top of our tree.
Return total_sum: After the dfs function has explored the entire relevant parts of the tree, total_sum will hold our final answer!

This strategy ensures we only visit the necessary nodes, significantly speeding up our search!

💻 The Code

Here's how we can implement this elegant solution in Python:

# 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:
        # Initialize our total sum
        total_sum = 0

        # Define our recursive Depth-First Search (DFS) helper function
        def dfs(node):
            # We use 'nonlocal' because total_sum is defined in the outer function's scope,
            # and we want to modify that specific variable, not create a new local one.
            nonlocal total_sum 

            # Base case: If the node is empty, there's nothing to process.
            if not node:
                return

            # 1. Check if the current node's value is within our target range [low, high]
            if low <= node.val <= high:
                total_sum += node.val

            # 2. Pruning and deciding where to go next:
            # Only traverse the left subtree if its values *could* be >= low.
            # If node.val is already less than low, then its left children (even smaller)
            # definitely won't be in range, so we don't go left.
            if node.val > low:
                dfs(node.left)

            # Only traverse the right subtree if its values *could* be <= high.
            # If node.val is already greater than high, then its right children (even larger)
            # definitely won't be in range, so we don't go right.
            if node.val < high:
                dfs(node.right)

        # Start the DFS traversal from the root of the tree
        dfs(root)

        # After visiting all relevant nodes, return the calculated total_sum
        return total_sum

⏱️ Complexity Analysis

Understanding how efficient your code is is a crucial part of competitive programming!

Time Complexity: O(N)
- In the worst-case scenario, where the low and high range covers almost all or all nodes in the tree (e.g., low=1, high=10^5), we might still have to visit every single node. Even with pruning, if all nodes are in range, or the pruning only happens at the very edges, we essentially traverse the whole tree. N is the number of nodes in the tree.
- However, due to the clever pruning with the BST property, on average, we visit significantly fewer nodes than N if the range is narrow and located centrally within the tree.
Space Complexity: O(H)
- This represents the space taken by the recursion call stack. H is the height of the tree.
- In the worst case (a "skewed" tree, essentially a linked list where all nodes are on one side), H can be equal to N. So, the space complexity would be O(N).
- In the best case (a perfectly balanced tree), H is log N. So, the space complexity would be O(log N).

💡 Key Takeaways

BSTs are Your Friends! Always remember the left < parent < right property. It's not just a definition; it's a powerful tool for optimizing search and traversal algorithms.
Recursion for Trees: Many tree problems lend themselves beautifully to recursive solutions. Think about the base case and how to process the current node before making recursive calls for its children.
Pruning for Performance: Don't just traverse blindly! Look for opportunities to eliminate entire branches of a tree (or parts of any data structure) that you know won't contain your target. This "pruning" is a fantastic way to make your algorithms much faster.

This problem is a fantastic introduction to leveraging data structure properties for efficient algorithms. Keep practicing, and you'll be a tree master in no time!

Happy coding! 🚀

Authored by Vansh2710
Published on 2026-04-17 00:07:04

DEV Community