Problem Description

You are given the root node of a binary search tree (BST) and two integers low and high. Your task is to find the sum of values of all nodes whose values fall within the inclusive range [low, high].

In other words, you need to traverse the BST and add up the values of all nodes where the node's value is greater than or equal to low and less than or equal to high.

The solution uses a depth-first search (DFS) approach that takes advantage of the BST property. Since it's a BST, for any node:

• All values in the left subtree are smaller than the node's value
• All values in the right subtree are larger than the node's value

The algorithm works as follows:

1. If the current node is None, return 0

2. Check if the current node's value x is within the range [low, high]. If yes, add it to the answer; otherwise, start with 0

3. If x > low, there might be valid nodes in the left subtree (since left subtree has smaller values that could still be ≥ low), so recursively explore the left subtree

4. If x < high, there might be valid nodes in the right subtree (since right subtree has larger values that could still be ≤ high), so recursively explore the right subtree

5. Return the accumulated sum

This approach efficiently prunes branches that cannot contain values within the desired range, making it more efficient than traversing the entire tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary search tree is a special type of graph where each node has at most two children (left and right). Trees are a subset of graphs with no cycles and a hierarchical structure.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary search tree (BST). A BST is a tree data structure where each node follows the ordering property: left child values are less than the parent, and right child values are greater than the parent.

DFS

• We arrive at DFS: Since we're dealing with a tree structure and need to traverse nodes to calculate the sum of values within a range, DFS is the appropriate approach.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this tree traversal problem. DFS is ideal here because:

1. We need to visit nodes in the tree to check if their values fall within the given range [low, high]
2. The BST property allows us to intelligently prune branches during traversal (if a node's value is less than low, we don't need to explore its left subtree for values in range)
3. DFS naturally handles the recursive nature of tree traversal, making it straightforward to accumulate the sum as we visit valid nodes

Intuition

When we need to find the sum of node values within a range in a BST, the key insight is to leverage the BST's ordering property to make our search more efficient.

Think about how a BST is structured: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property gives us valuable information about where to look for nodes within our target range [low, high].

Consider what happens when we visit a node with value x:

1. If x is within [low, high], we include it in our sum. But we still need to check both subtrees because there might be valid values on both sides.

2. If x < low, this node is too small. More importantly, since all values in the left subtree are even smaller than x, none of them can be within our range. We only need to check the right subtree where larger values exist.

3. If x > high, this node is too large. Similarly, all values in the right subtree are even larger, so we can skip them entirely and only check the left subtree.

This leads us to a selective traversal strategy:

• When x > low, explore the left subtree (because there might be values ≥ low there)
• When x < high, explore the right subtree (because there might be values ≤ high there)

This is more efficient than blindly traversing the entire tree. We're essentially "pruning" branches that we know cannot contain values in our target range. The DFS approach naturally fits this recursive exploration pattern where we make decisions at each node about which subtrees are worth exploring.

The beauty of this solution is that it combines the BST property with conditional traversal to avoid unnecessary work, making the algorithm both elegant and efficient.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS function to traverse the BST and accumulate the sum of nodes within the range [low, high].

Let's walk through the implementation step by step:

1. Define the DFS Helper Function

We create a nested function dfs(root) that returns the sum of all node values in the subtree rooted at root that fall within the range [low, high].

2. Base Case

if root is None:
    return 0

When we reach a null node, we return 0 as there's nothing to add to our sum.

3. Check Current Node's Value

x = root.val
ans = x if low <= x <= high else 0

We extract the current node's value x and check if it's within the range. If low <= x <= high, we include it in our answer; otherwise, we start with 0.

4. Selective Traversal Based on BST Property

if x > low:
    ans += dfs(root.left)

If x > low, there might be nodes in the left subtree with values >= low (since left subtree contains smaller values than x). So we recursively explore the left subtree and add its result to our answer.

if x < high:
    ans += dfs(root.right)

If x < high, there might be nodes in the right subtree with values <= high (since right subtree contains larger values than x). So we recursively explore the right subtree and add its result to our answer.

5. Return the Result

return ans

We return the accumulated sum for the current subtree.

Key Optimization:

The clever part of this solution is the pruning logic:

• When x <= low, we skip the left subtree entirely (all values there are < x <= low)
• When x >= high, we skip the right subtree entirely (all values there are > x >= high)

This pruning significantly reduces the number of nodes visited compared to a naive approach that would traverse the entire tree.

Time Complexity: O(n) in the worst case where all nodes are within range, but typically better due to pruning.

Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.

Example Walkthrough

Let's walk through the algorithm with a concrete example. Consider this BST with low = 7 and high = 15:

       10
      /  \
     5    15
    / \     \
   3   7    18

We want to find the sum of all nodes with values in the range [7, 15].

Step 1: Start at root (value = 10)

• Check: Is 10 in [7, 15]? Yes! Add 10 to our sum. ans = 10
• Since 10 > 7 (10 > low), explore left subtree
• Since 10 < 15 (10 < high), explore right subtree

Step 2: Explore left subtree (root = 5)

• Check: Is 5 in [7, 15]? No. ans = 0 for this node
• Since 5 < 7 (5 < low), skip left subtree entirely (all values there are < 5 < 7)
• Since 5 < 15 (5 < high), explore right subtree

Step 3: Visit node 7

• Check: Is 7 in [7, 15]? Yes! Return 7
• Since 7 = 7 (7 = low), skip left subtree
• Since 7 < 15 (7 < high), explore right subtree (which is null, returns 0)
• Return 7 to parent

Step 4: Back to node 5

• Node 5 returns: 0 (its own value) + 7 (from right child) = 7

Step 5: Explore right subtree from root (node = 15)

• Check: Is 15 in [7, 15]? Yes! ans = 15
• Since 15 > 7 (15 > low), explore left subtree (which is null, returns 0)
• Since 15 = 15 (15 = high), skip right subtree entirely (all values > 15)
• Return 15

Step 6: Combine results at root

• Root returns: 10 (its own value) + 7 (from left subtree) + 15 (from right subtree) = 32

Final Answer: 32

Notice how we intelligently pruned branches:

• We never visited node 3 (skipped when at node 5 since 5 < low)
• We never visited node 18 (skipped when at node 15 since 15 = high)

This pruning makes our algorithm more efficient than blindly traversing every node.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary search tree.

In the worst case, the algorithm visits every node in the tree exactly once. Even though the code has optimizations that skip certain subtrees based on BST properties (when x <= low, it skips the left subtree; when x >= high, it skips the right subtree), the worst-case scenario occurs when all nodes fall within the range [low, high]. In this case, every node must be visited to calculate the sum, resulting in O(n) time complexity.

Space Complexity: O(n) where n is the number of nodes in the binary search tree.

The space complexity is determined by the recursive call stack. In the worst case, the tree could be completely unbalanced (essentially a linked list), causing the recursion depth to reach n levels. Each recursive call adds a frame to the call stack, consuming O(1) space per frame. Therefore, the maximum space used by the call stack is O(n) in the worst case. In the best case of a balanced tree, the space complexity would be O(log n), but we consider the worst-case complexity here.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Pruning Logic - Using Wrong Comparison Operators

One of the most common mistakes is getting the pruning conditions backwards or using the wrong comparison operators. Developers often write:

Incorrect Implementation:

# WRONG: Using >= and <= for pruning conditions
if current_val >= low:  # Should be >
    current_sum += dfs(node.left)
if current_val <= high:  # Should be <
    current_sum += dfs(node.right)

Why This Is Wrong:

• When current_val == low, all values in the left subtree are < low (due to BST property), so exploring the left subtree is unnecessary
• When current_val == high, all values in the right subtree are > high, so exploring the right subtree is unnecessary
• Using >= and <= causes unnecessary traversals and defeats the optimization

Correct Implementation:

# CORRECT: Use strict inequalities for pruning
if current_val > low:
    current_sum += dfs(node.left)
if current_val < high:
    current_sum += dfs(node.right)

2. Forgetting to Add Current Node's Value When in Range

Another pitfall is exploring the subtrees correctly but forgetting to include the current node's value when it falls within the range:

Incorrect Implementation:

def dfs(node):
    if node is None:
        return 0
  
    current_sum = 0  # WRONG: Not checking if current node is in range
  
    if node.val > low:
        current_sum += dfs(node.left)
    if node.val < high:
        current_sum += dfs(node.right)
  
    return current_sum

Correct Implementation:

def dfs(node):
    if node is None:
        return 0
  
    # CORRECT: Check and add current node's value if in range
    current_sum = node.val if low <= node.val <= high else 0
  
    if node.val > low:
        current_sum += dfs(node.left)
    if node.val < high:
        current_sum += dfs(node.right)
  
    return current_sum

3. Using 'elif' Instead of Independent 'if' Statements

Some developers mistakenly use elif for the second pruning condition:

Incorrect Implementation:

if current_val > low:
    current_sum += dfs(node.left)
elif current_val < high:  # WRONG: Should be 'if', not 'elif'
    current_sum += dfs(node.right)

Why This Is Wrong:

• When a node's value is within the range (e.g., low < current_val < high), we need to explore BOTH subtrees
• Using elif means we'll only explore one subtree even when both should be explored
• This leads to missing valid nodes and incorrect sums

Correct Implementation:

if current_val > low:
    current_sum += dfs(node.left)
if current_val < high:  # CORRECT: Independent 'if' allows both to execute
    current_sum += dfs(node.right)

Prevention Tips:

1. Test with edge cases: Use a BST where the root value equals low or high to verify pruning logic
2. Trace through small examples: Manually trace the algorithm on a small BST to ensure all valid nodes are visited
3. Remember the BST property: Always keep in mind that left < current < right to reason about pruning conditions