938. Range Sum of BST - Detailed Explanation

This checks all nodes without any early pruning. An iterative BFS/DFS would similarly push all children regardless of value. This brute-force solution is correct but not using the BST advantages, so it may do more work than necessary.

Approach 2: Optimized DFS (Using BST Properties)

Idea: Utilize the BST ordering to prune branches that we know cannot contain values in the range. We still traverse the tree, but we skip entire subtrees that are guaranteed to lie outside [low, high]. This significantly reduces unnecessary visits.

Method (Recursion): At each node, decide which way to go:

• If the current node is null, return 0 (no value).

• If the current node’s value is less than low, ignore its left subtree and recurse only into the right subtree (because all left values are smaller and thus < low).

• If the current node’s value is greater than high, ignore its right subtree and recurse only into the left subtree (because all right values are larger and thus > high).

• If the current node’s value is within [low, high], then take its value into the sum and recurse into both left and right children (because there might be more values in range on both sides).

This logic can be implemented succinctly. For example, in pseudocode (or a return-value style recursion):

function rangeSumBST(node, low, high):
    if node is null: 
        return 0
    if node.val < low:
        # Node value too small, ignore left subtree
        return rangeSumBST(node.right, low, high)
    if node.val > high:
        # Node value too large, ignore right subtree
        return rangeSumBST(node.left, low, high)
    # Node is in range:
    return node.val 
           + rangeSumBST(node.left, low, high) 
           + rangeSumBST(node.right, low, high)

This way, you never even call the function on a subtree that you know is out of range . The approach ensures we only traverse paths that could have in-range nodes. An iterative version can use a stack/queue with the same conditions before pushing children.

Example: Using this optimized strategy on Example 1: at the root (10, in range), you would add 10 and explore both sides. The left child 5 is below the range, so you skip 5’s left subtree entirely (skipping node 3 and its children) and move to 5’s right child. The right child 15 is within range, so you include 15 and explore its left (which is null) and skip its right subtree (since 18 is above the range). This yields the sum 32 while avoiding unnecessary traversal of node 3 and 18. (We will walk through a detailed example in the walkthrough section.)

Note: In an iterative implementation, you would use the same logic when pushing children onto a stack. For instance, only push the left child if node.val > low and only push the right child if node.val < high. It’s important not to use mutually exclusive if-elif in this case – you might need to consider both children when the node’s value is in range. For example, in the recursive pseudocode above, we handle the in-range case separately so that we explore both sides. In an iterative code, that translates to using two separate if statements (not elif) so that both left and right children can be added when appropriate.

Code Implementation

Python Implementation

Both approaches produce the same correct result. The optimized version avoids unnecessary recursion into parts of the tree that don’t contain values in the range.

Complexity Analysis

• Time Complexity: Both approaches run in O(n) time in the worst case, where n is the number of nodes in the tree. This is because in the worst-case scenario (e.g., if [low, high] covers all node values or the tree is very skewed), the algorithm needs to visit every node. The brute-force approach always visits all n nodes. The optimized approach can be faster on average by pruning branches, but it still has O(n) worst-case complexity – for a single query on a BST, you cannot do better than O(n) time without additional data structures or preprocessing. In balanced trees with a narrow range, the optimized approach might visit only a fraction of the nodes (for example, O(h) or O(k) nodes, where k is number of nodes in range), but Big-O worst-case remains linear.

• Space Complexity: The additional space depends on the recursion or iteration stack. In the worst case (skewed tree of height n), the stack can grow to O(n). For a balanced tree, the recursion depth (or stack size) is O(h) = O(log n). The brute-force approach uses space for recursion stack similarly (O(n) worst-case). The optimized approach also uses O(n) stack space in the worst case (when no pruning is possible, e.g., the range covers the entire tree or the tree is skewed). If using an explicit stack/queue, that too is O(n) in the worst case.

• Memory Optimizations: Without changing the problem constraints, we typically accept O(n) space for traversal. However, there is an advanced technique called Morris Inorder Traversal that can achieve O(1) auxiliary space for tree traversal (by temporarily modifying the tree structure). It can be applied to inorder-traverse the BST without recursion or a stack, and one could integrate the range-sum logic into that. Using Morris traversal would keep the time O(n) but reduce stack space to O(1). This optimization is complex and not necessary for solving the problem, but it’s an interesting note for reducing recursion/stack usage.

Step-by-Step Walkthrough (Example)

Let's walk through the optimized approach on Example 1 (low=7, high=15) to see how it works in detail. The BST for Example 1 is visualized below:

1. Start at the root (10): 10 is between 7 and 15, so it falls in the range. We include 10 in our sum. Now sum = 10. Since 10 is within range, we need to explore both subtrees. (If 10 were less than 7, we’d skip left; if greater than 15, we’d skip right. But here we go both ways.)

2. Go to the left child (5): Node value 5 is less than the low bound (5 < 7). This means not only is 5 itself out of range (we do not add it), but every node in 5’s left subtree is guaranteed to be < 5, hence also out of range [7,15]. We can prune that entire left subtree. In this case, 5’s left child is 3, and indeed 3 < 7, so skipping is correct. We do check 5’s right child, because there could be values ≥5 there. (We know 5 < 7, but maybe a descendant on the right is larger.) We do not add 5 to the sum. sum remains 10.

3. Explore 5’s right subtree (node 7): The right child of 5 is 7. Now, 7 is within [7,15] (it equals the low bound). We include 7 in the sum. Now sum = 10 + 7 = 17. Since 7 is in range, we check both of its children. Node 7 in this tree is a leaf (no children), so there are no further nodes down this path. (If 7 had children, we would skip its left child if it existed, because any left child <7 would be below the low bound. We would explore a right child if it existed, since values >7 might still be ≤15.)

4. Backtrack to root (10) after finishing the left subtree. We have now processed all nodes in the left subtree of 10 that could be in range (we skipped 3 and 5, but processed 7). The partial sum is 17.

5. Go to the right child of root (15): Node value 15 is ≤ 15 and ≥ 7, so it is in range (it equals the high bound). We add 15 to the sum. Now sum = 17 + 15 = 32. Because 15 is within range, we would normally explore both children. However, 15’s right child is 18, and since 18 is greater than the high bound 15, we know that entire right subtree of 15 is out of range. We prune the right subtree of 15 without traversing it (skipping node 18 and anything below it). We do check 15’s left child (if any) because values left of 15 are <15 and could be ≥7. In this example, 15’s left child is null, so there’s nothing to do on the left side.

6. Traversal complete: We have visited all nodes that could possibly be in the range, and pruned those that are guaranteed out of range. The final sum we accumulated is 32, which matches the expected output. We never visited node 3 (pruned at step 2) or node 18 (pruned at step 5) at all during the traversal, thanks to the BST-based optimizations.

By following the above steps, we see how the algorithm efficiently skips over sections of the tree. In summary, nodes 10, 7, and 15 were visited and counted, while nodes 3, 5, and 18 were either skipped or not added due to being out of range, yielding the correct sum 32.

(You can similarly trace Example 2 to verify that the algorithm visits nodes 10, 7, 6 (from the left subtree) and skips others, accumulating 23.)

Common Mistakes and Pitfalls

• Using Wrong Conditional Structure: A common implementation mistake is using an if-elif-else chain incorrectly and thereby skipping needed branches. For example, if you write:

  if (node.val < low) {
      // go right
  } else if (node.val > high) {
      // go left
  } else {
      // in range: add value
      // go left and go right
  }

  This looks correct – and it is one valid approach. But if you try a different structure in an iterative solution like:

  if (node.val >= low && node.val <= high) { sum += node.val; }
  else if (node.val < low) { ... }
  else if (node.val > high) { ... }
  // then push children...

  you might inadvertently skip pushing a child that should be explored. It’s safer to handle the in-range case separately or use separate if statements for pushing left and right children. In an iterative solution, do not use if-else for the child pushes — use two independent if checks (one for left, one for right) so that both children can be considered when the node is in range.

• Not Including Boundaries: Make sure to use inclusive checks. Forgetting to allow equality (>= or <=) for low or high will drop nodes that are exactly equal to the boundaries. For instance, if low = 5 and a node value is 5, it should be counted. Using strict < low or > high checks appropriately (or the equivalent logic) ensures inclusion of boundary values.

• Ignoring the BST Property: While not incorrect, ignoring the BST ordering (as in the brute force approach) is a missed optimization. It won’t cause a wrong answer, but it could cause time-outs in other contexts with larger constraints. Always check if the tree’s properties (BST, heap, etc.) can be used to simplify the problem.

• Global Sum in Recursion: If you use a global or class-level variable to accumulate the sum during recursion, be careful to reset it between test cases or separate function calls. A common mistake in coding contests is to use a static global sum that isn’t reset to 0 before computing a new range sum. This leads to incorrect results on subsequent runs. To avoid this, either reset the global variable or use the return-value style recursion as shown above (which naturally handles sum in each call’s return value).

• Deep Recursion Risk: If the BST is highly skewed (like a linked list) with 20,000 nodes, a naive recursive solution in a language like Python could hit recursion depth limits (default limit is around 1000). This might cause a runtime error. In practice, LeetCode’s input distribution might not include such a pathological case, but it’s something to be mindful of. Using an iterative approach with an explicit stack can circumvent this issue for extremely deep trees.

Edge Cases to Consider

• Empty Tree: If root is None (null), the sum should obviously be 0. Our functions handle this by immediately returning 0 when the node is null.

• Single Node Tree: If the BST has only one node, the function should return that node’s value if it lies in the range, or 0 if it doesn’t. For example, a tree with just a node 5 and range [5,5] should return 5; range [6,10] should return 0.

• All Nodes Out of Range: If no node falls within [low, high], the result should be 0. For instance, if the tree has values all less than 10 but low is 10, nothing qualifies. The algorithm naturally handles this by never adding any values (all checks fail), resulting in 0.

• All Nodes In Range: If the range covers the entire set of node values (e.g., low is smaller or equal to the minimum node and high is larger or equal to the maximum node in the BST), then the sum should include every node. The optimized approach will still traverse the whole tree in this case (pruning doesn’t apply), effectively behaving like the brute force. Ensure that your implementation doesn’t accidentally prune in these extreme cases. The output should simply be the sum of all node values.

• low == high: The range could be a single value. Then the task reduces to finding if that value exists in the BST (and possibly multiple occurrences if it were not a BST with unique values). The sum in this case will just be that value if found, otherwise 0. The algorithm handles this seamlessly – it will search the tree and only add when it finds that exact value. (For example, in Example 1, if low=7 and high=7, the output would be 7, coming from the node with value 7.)

• Duplicate Values: By problem constraints, the BST has unique values. If a similar problem allowed duplicates (not as a BST, or a multiset tree), the logic of checking both subtrees for in-range nodes would still work, but counting duplicates would naturally happen as you traverse each occurrence. Just be aware that BSTs typically don’t contain duplicates (or handle them in a specific way like all duplicates to one side).

Alternative Variations and Related Problems

• Count of Nodes in Range: Instead of summing values, a variation is to count how many nodes fall within a given range. The approach is almost identical, except you increment a counter rather than adding node values. For example, one problem asks: “Given a BST and integers lo and hi, return the count of all nodes whose values are between lo and hi (inclusive).” You can solve it by traversing with the same pruning logic, just counting nodes. (In the Example 1 tree with range [7,15], the count would be 3, since three nodes have values in that range.)

• Print BST Keys in Range: Another related task is to print or collect all the node values within a range, instead of summing them. You would use the same traversal strategy. If you do an inorder traversal while applying the range filter, you will get the output in sorted order (which is sometimes desired). GeeksforGeeks, for instance, has a problem that asks to print all keys of a BST in a given range [k1, k2]. The solution logic is: (1) if current node value is greater than k1, recurse left, (2) if current node is in range, output it, (3) if current node value is less than k2, recurse right. This is exactly the in-order variant of our approach.

• Trim a BST: LeetCode 669 “Trim a Binary Search Tree” is a complementary problem. Instead of summing or listing the nodes in a range, you are asked to remove all nodes not in a given range and return the pruned BST. The input is a BST and bounds L and R, and you must return the root of the BST that contains only values in [L, R] (all others are trimmed out). The approach to solve this is very similar: you recursively prune left or right subtrees when a node is out of range, and link the returned trimmed subtrees accordingly. It uses the same idea of skipping branches using BST properties.

• Range Sum Queries on BST (Multiple Queries): In some scenarios, you might need to answer many range-sum queries on a static BST. Doing the above traversal for each query would be O(n) per query. To optimize multiple queries, one could augment the BST nodes with additional information, such as the sum of the subtree rooted at that node. This turns the BST into something like an “order statistic tree” or Fenwick tree, enabling quicker range sum lookups. While this is an advanced variation (not a LeetCode problem, but a typical data structure extension), it’s a good practice problem to think about: augmenting trees for range-sum or order-statistic queries.

• Other BST Practice Problems: To build more intuition with BST properties, you might try problems like “Lowest Common Ancestor of a BST” (LeetCode 235) or “Validate BST”. These are not range-sum problems, but they rely on navigating the tree according to value comparisons. They will further strengthen your understanding of how to leverage the BST invariant (e.g., moving left or right based on comparisons) in problem solving.