LeetCode 938 - Range Sum of BST

This problem gives us the root of a Binary Search Tree, abbreviated as BST, along with two integers, low and high. We must compute the sum of all node values whose values lie inside the inclusive range [low, high].

leetcodeeasytreedepth-first-searchbinary-search-treebinary-tree

LeetCode Problem 938

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem gives us the root of a Binary Search Tree, abbreviated as BST, along with two integers, low and high. We must compute the sum of all node values whose values lie inside the inclusive range [low, high].

A Binary Search Tree has an important property:

  • Every node in the left subtree has a smaller value than the current node.
  • Every node in the right subtree has a larger value than the current node.

This ordering property is the key observation that allows us to solve the problem efficiently.

The input consists of:

  • root, which is the root node of the BST
  • low, the lower bound of the allowed range
  • high, the upper bound of the allowed range

The output is a single integer representing the sum of all node values such that:

low <= node.val <= high

The constraints tell us several important things:

  • The tree can contain up to 2 * 10^4 nodes, so the solution should ideally be linear or close to linear.
  • Node values are unique, which simplifies reasoning because we never need to handle duplicate values.
  • Values can be as large as 10^5, but this does not significantly affect the algorithm choice because we are traversing nodes, not indexing by value.

An important detail is that this is specifically a BST, not just a regular binary tree. A naive implementation may ignore this property and traverse every node. While that still works, it misses an optimization opportunity.

Several edge cases are worth considering:

  • The tree may contain only one node.
  • Every node may fall inside the range.
  • No node may fall inside the range.
  • The valid range may only include leaf nodes.
  • The BST may be heavily skewed, behaving like a linked list.

The problem guarantees that the tree contains at least one node and that all node values are unique.

Approaches

Brute Force Approach

The brute force solution is straightforward. We perform a complete traversal of the tree, visiting every node regardless of its value.

For each node:

  • If its value lies within [low, high], we add it to the running sum.
  • Otherwise, we ignore it.

A depth first traversal such as preorder, inorder, or postorder all work equally well because every node must eventually be checked.

This approach is correct because it explicitly evaluates every node and includes exactly those nodes that satisfy the range condition.

However, this solution ignores the BST property. Even if an entire subtree cannot possibly contain valid values, the algorithm still traverses it. That unnecessary work becomes inefficient for large trees.

Optimal Approach Using BST Pruning

The BST ordering property allows us to skip entire subtrees.

Consider a node with value x:

  • If x < low, then every value in the left subtree is also less than low, because all left subtree values are smaller than x. Therefore, the entire left subtree can be skipped.
  • If x > high, then every value in the right subtree is also greater than high, so the entire right subtree can be skipped.
  • If low <= x <= high, then the current node contributes to the sum, and both subtrees may still contain valid nodes.

This pruning drastically reduces unnecessary traversal.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(h) Visits every node regardless of BST ordering
Optimal O(n) worst case, often much better O(h) Uses BST property to prune unnecessary subtrees

Here:

  • n is the number of nodes
  • h is the height of the tree

In balanced trees, the pruning often eliminates large portions of the tree.

Algorithm Walkthrough

  1. Start a recursive DFS traversal from the root node.
  2. If the current node is None, return 0.

This is the base case. An empty subtree contributes nothing to the sum. 3. If the current node value is smaller than low, recursively search only the right subtree.

Since this is a BST, every node in the left subtree is even smaller, so none of them can belong to the valid range. 4. If the current node value is greater than high, recursively search only the left subtree.

Every node in the right subtree is even larger, so the right subtree can be ignored completely. 5. Otherwise, the current node lies inside the range.

Add the current node value to the sums returned from both left and right recursive calls. 6. Return the computed sum back to the caller.

Why it works

The algorithm works because the BST property guarantees ordering within subtrees.

Whenever a node value is smaller than low, the entire left subtree is guaranteed to contain invalid values. Similarly, when a node value is larger than high, the entire right subtree is guaranteed to contain invalid values.

Therefore, the algorithm never skips a subtree that could contain valid values, and it never includes nodes outside the range. This guarantees correctness.

Python Solution

# 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

from typing import Optional

class Solution:
    def rangeSumBST(
        self,
        root: Optional["TreeNode"],
        low: int,
        high: int
    ) -> int:

        def dfs(node: Optional["TreeNode"]) -> int:
            if node is None:
                return 0

            if node.val < low:
                return dfs(node.right)

            if node.val > high:
                return dfs(node.left)

            return (
                node.val
                + dfs(node.left)
                + dfs(node.right)
            )

        return dfs(root)

The implementation uses a recursive helper function named dfs.

The first condition handles the base case. If the node is None, the subtree contributes zero to the sum.

The second condition checks whether the node value is smaller than low. In that case, the entire left subtree is skipped because all values there are guaranteed to be even smaller.

The third condition checks whether the node value is larger than high. Then the algorithm skips the right subtree for the same reason.

If neither condition applies, the node lies within the valid range. The algorithm adds the current node value and recursively explores both subtrees.

The final answer is returned by calling dfs(root).

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func rangeSumBST(root *TreeNode, low int, high int) int {
    var dfs func(node *TreeNode) int

    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        if node.Val < low {
            return dfs(node.Right)
        }

        if node.Val > high {
            return dfs(node.Left)
        }

        return node.Val + dfs(node.Left) + dfs(node.Right)
    }

    return dfs(root)
}

The Go implementation follows the same recursive logic as the Python solution.

The primary language difference is handling nil pointers instead of None.

Go also requires explicitly declaring the recursive function variable before assigning the function definition, which is why:

var dfs func(node *TreeNode) int

appears before the function body.

Integer overflow is not an issue here because the maximum possible sum remains well within Go's standard integer range.

Worked Examples

Example 1

Input:

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

Tree structure:

        10
       /  \
      5    15
     / \     \
    3   7     18

Step by step traversal:

Current Node Action Running Sum
10 Inside range, include it 10
5 Smaller than low, skip left subtree 10
7 Inside range, include it 17
15 Inside range, include it 32
18 Greater than high, skip right subtree 32

Final answer:

32

Example 2

Input:

root = [10,5,15,3,7,13,18,1,null,6]
low = 6
high = 10

Tree structure:

           10
         /    \
        5      15
       / \    /  \
      3   7  13  18
     /   /
    1   6

Step by step traversal:

Current Node Action Running Sum
10 Inside range 10
5 Smaller than low, skip left subtree 10
7 Inside range 17
6 Inside range 23
15 Greater than high, skip right subtree 23
13 Greater than high 23

Final answer:

23

Complexity Analysis

Measure Complexity Explanation
Time O(n) worst case Every node may still be visited in the worst case
Space O(h) Recursive call stack height equals tree height

The worst case occurs when:

  • The tree is completely skewed, or
  • Nearly all nodes fall within the range

In balanced trees, pruning often reduces the number of visited nodes significantly, although the theoretical worst case remains O(n).

The recursion stack uses O(h) space, where h is the height of the tree. In balanced trees, this becomes O(log n). In skewed trees, it can degrade to O(n).

Test Cases

# Definition for testing
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, low, high):
        def dfs(node):
            if node is None:
                return 0

            if node.val < low:
                return dfs(node.right)

            if node.val > high:
                return dfs(node.left)

            return node.val + dfs(node.left) + dfs(node.right)

        return dfs(root)

sol = Solution()

# Example 1
root1 = TreeNode(
    10,
    TreeNode(
        5,
        TreeNode(3),
        TreeNode(7)
    ),
    TreeNode(
        15,
        None,
        TreeNode(18)
    )
)
assert sol.rangeSumBST(root1, 7, 15) == 32  # standard example

# Example 2
root2 = TreeNode(
    10,
    TreeNode(
        5,
        TreeNode(
            3,
            TreeNode(1)
        ),
        TreeNode(
            7,
            TreeNode(6)
        )
    ),
    TreeNode(
        15,
        TreeNode(13),
        TreeNode(18)
    )
)
assert sol.rangeSumBST(root2, 6, 10) == 23  # second example

# Single node inside range
root3 = TreeNode(8)
assert sol.rangeSumBST(root3, 5, 10) == 8  # one node counted

# Single node outside range
root4 = TreeNode(8)
assert sol.rangeSumBST(root4, 9, 12) == 0  # one node excluded

# Entire tree inside range
root5 = TreeNode(
    5,
    TreeNode(3),
    TreeNode(8)
)
assert sol.rangeSumBST(root5, 1, 10) == 16  # all nodes included

# No nodes inside range
root6 = TreeNode(
    5,
    TreeNode(3),
    TreeNode(8)
)
assert sol.rangeSumBST(root6, 10, 20) == 0  # empty valid set

# Left-skewed tree
root7 = TreeNode(
    5,
    TreeNode(
        4,
        TreeNode(
            3,
            TreeNode(2)
        )
    )
)
assert sol.rangeSumBST(root7, 2, 4) == 9  # skewed structure

# Right-skewed tree
root8 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(
            3,
            None,
            TreeNode(4)
        )
    )
)
assert sol.rangeSumBST(root8, 2, 3) == 5  # skewed opposite direction

# Range matches exact node values
root9 = TreeNode(
    10,
    TreeNode(5),
    TreeNode(15)
)
assert sol.rangeSumBST(root9, 5, 15) == 30  # inclusive bounds
Test Why
Example 1 Validates normal BST traversal and pruning
Example 2 Verifies deeper subtree traversal
Single node inside range Ensures minimal valid tree works
Single node outside range Ensures exclusion logic works
Entire tree inside range Confirms all nodes are counted
No nodes inside range Confirms zero result handling
Left-skewed tree Tests recursion depth on skewed BST
Right-skewed tree Tests opposite skew direction
Range matches exact node values Verifies inclusive boundaries

Edge Cases

Single Node Tree

A tree with only one node is the smallest valid input. This case can expose bugs where recursive base cases are handled incorrectly.

If the single node lies inside the range, the algorithm returns its value. Otherwise, it returns 0. The implementation handles this naturally because the recursion immediately evaluates the root and terminates.

No Values Inside the Range

It is possible that every node value lies outside [low, high].

A naive implementation may still traverse the entire tree unnecessarily. The optimized BST solution avoids much of that work through pruning. For example, if all node values are smaller than low, the algorithm repeatedly skips left subtrees and moves only to the right.

The implementation correctly returns 0 because no node satisfies the inclusion condition.

Highly Skewed Tree

A BST may become completely unbalanced, effectively turning into a linked list.

For example:

1
 \
  2
   \
    3
     \
      4

This case is important because recursion depth becomes O(n) instead of O(log n).

The implementation still produces the correct answer because the recursive logic does not rely on tree balance. However, the recursion stack grows linearly with the height of the tree in this scenario.