---

1. Problem Summary

You are given the root of a Binary Search Tree (BST) and two integers low and high.

Your task is to compute the sum of all node values such that:

low <= node.val <= high

Important details:

• Tree obeys BST ordering: left subtree < node < right subtree
• You must include all values within the closed interval
• Tree may contain any number of nodes
• If no values lie within range, return 0

Example:

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

Nodes in range: 7, 10, 15
Sum = 32

---

2. Key Insights

Insight 1: BST ordering allows pruning

Because:

left subtree values < node.val < right subtree values

We can skip entire subtrees:

• If node.val < low → ignore left subtree
• If node.val > high → ignore right subtree

Insight 2: Better than traversing entire tree

Full traversal costs O(N), but pruning yields faster performance on average.

Insight 3: DFS works naturally

We recursively explore relevant subtrees only.

Insight 4: BFS also possible but less efficient logically

DFS matches tree structure better.

Insight 5: Range can include endpoints

Use >= and <= comparisons.

---

3. Approach

DFS with pruning based on BST properties

Steps:

1. If node is null → return 0
2. If node.val < low:
   • skip left subtree
   • recurse right subtree
3. If node.val > high:
   • skip right subtree
   • recurse left subtree
4. Otherwise (node value within range):
   • sum = node.val + recurse left + recurse right

Return total.

---

4. Time and Space Complexity

Time Complexity:

O(N) worst case
O(log N) best case with pruning and balanced tree

Space Complexity:

O(H)

Where H = tree height (recursion depth)

Worst case skewed: O(N)
Balanced tree: O(log N)

---

5. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }

        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }

        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }

        return root.val
             + rangeSumBST(root.left, low, high)
             + rangeSumBST(root.right, low, high);
    }
}

---

6. Dry Run Examples

Example 1

Input:

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

Traversal reasoning:

• 10 in range → include
• explore left (5)
• 5 < low → skip left subtree, explore right (7)
• 7 in range → include
• explore right subtree from 10 (15,18)
• 15 in range → include
• 18 > high → skip

Sum:

10 + 7 + 15 = 32

Output:

32

---

Example 2

Input:

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

Nodes counted: 7, 10

Output:

17

---

Example 3

Input:

[1]
low = 1, high = 2

Node is in range

Output:

1

---

Example 4

Input:

[5,3,8,2,4,7,9]
low = 20, high = 30

No values in range

Output:

0

---

Example 5

Input:

[15,10,20,5,13,18,25]
low = 12, high = 24

Values included: 13, 15, 18, 20

Output:

66

---

7. Why This Solution Works

• BST ordering guarantees correctness of pruning
• Traversal only explores necessary branches
• Reduces search space significantly
• Handles:
  • exact boundary matches
  • empty trees
  • skewed and balanced trees

---

8. Common Mistakes

1. Traversing entire tree unnecessarily
2. Using < instead of <= for range
3. Forgetting null check before accessing node fields
4. Adding values outside the range
5. Assuming BST may contain duplicates (problem definition implies standard BST)