# Range Sum of BST
**Difficulty:** EASY
[External](https://leetcode.com/problems/range-sum-of-bst)
Canonical: https://scaleengineer.com/dsa/problems/range-sum-of-bst
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
Given the `root` node of a binary search tree and two integers `low` and `high`, return _the sum of values of all nodes with a value in the **inclusive** range_ `[low, high]`.

**Example 1:**

![](https://assets.glich.co/dsa/range-sum-of-bst/image0.jpg) 

**Input:** root = [10,5,15,3,7,null,18], low = 7, high = 15
**Output:** 32
**Explanation:** Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

**Example 2:**

![](https://assets.glich.co/dsa/range-sum-of-bst/image1.jpg) 

**Input:** root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
**Output:** 23
**Explanation:** Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 2 * 104]`.
* `1 <= Node.val <= 105`
* `1 <= low <= high <= 105`
* All `Node.val` are **unique**.

# Approaches
## Brute-Force Tree Traversal
This approach involves traversing the entire binary tree, node by node, without taking advantage of the Binary Search Tree (BST) properties. For each visited node, we check if its value falls within the given range `[low, high]`. If it does, we add its value to a running total. Any standard tree traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) can be used.
**Time:** O(N), where N is the total number of nodes in the tree. This is because we must visit every single node to check its value. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N). For a balanced tree, it would be O(log N).
**Pros:** Very simple to understand and implement.; It is a general solution that works for any binary tree, not just a BST.
**Cons:** Highly inefficient as it fails to use the ordering property of the BST.; It explores subtrees that cannot possibly contain values in the desired range, performing unnecessary work.
### Explanation
We can implement this using a recursive Depth-First Search (DFS).

We define a helper function that takes a node as input. The base case for the recursion is when the node is null. In the recursive step, we first check if the current node's value is within the inclusive range `[low, high]`. If it is, we add the value to our sum. Crucially, we then unconditionally make recursive calls for the left and right children of the current node, ensuring every node is visited.

This process continues until all nodes have been visited. The final sum is then returned.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;

    public int rangeSumBST(TreeNode root, int low, int high) {
        dfs(root, low, high);
        return sum;
    }

    private void dfs(TreeNode node, int low, int high) {
        if (node == null) {
            return;
        }
        if (node.val >= low && node.val <= high) {
            sum += node.val;
        }
        // Unconditionally traverse left and right subtrees
        dfs(node.left, low, high);
        dfs(node.right, low, high);
    }
}
```
### Algorithm
- Initialize a global or instance variable `sum` to 0.
- Define a recursive function `dfs(node, low, high)`.
- **Base Case**: If the `node` is null, simply return.
- **Processing**: Check if the current `node.val` is within the inclusive range `[low, high]`.
- If `node.val >= low && node.val <= high`, add `node.val` to the `sum`.
- **Recursive Step**: Unconditionally make recursive calls for both the left and right children: `dfs(node.left, low, high)` and `dfs(node.right, low, high)`.
- Start the process by calling `dfs(root, low, high)` from the main function.
- Return the final `sum`.

## Optimized Traversal with Pruning
This approach leverages the fundamental property of a Binary Search Tree (BST) to significantly improve efficiency. The property states that for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. By using this property, we can "prune" entire subtrees from our search if we know they cannot contain values within the `[low, high]` range.
**Time:** O(N) in the worst case, where N is the number of nodes. This happens when the range `[low, high]` includes all nodes in the tree. However, on average, the performance is much better. The number of visited nodes is proportional to the height of the tree plus the number of nodes whose values are in the range, i.e., O(H + K), where H is the tree height and K is the number of nodes in the range. · **Space:** O(H), where H is the height of the tree. For the recursive approach, this is the depth of the recursion stack. For the iterative approach, this is the maximum size of the stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
**Pros:** Significantly more efficient on average than the brute-force approach.; Effectively utilizes the core properties of a BST to prune the search space.; The solution is clean and logical.
**Cons:** The recursive version could theoretically cause a stack overflow on an extremely deep, unbalanced tree, although this is unlikely given the problem constraints.
### Explanation
We traverse the tree, but at each node, we make an intelligent decision about where to go next based on the BST property.

-   If the current node's value is **less than `low`**, we know that the current node and its entire left subtree are too small. Therefore, we only need to explore the **right subtree**.
-   If the current node's value is **greater than `high`**, we know that the current node and its entire right subtree are too large. Therefore, we only need to explore the **left subtree**.
-   If the current node's value is **within the range `[low, high]`**, we add its value to our sum. Since values in both the left and right subtrees could potentially also be in the range, we must explore **both subtrees**.

This pruning strategy avoids visiting nodes that are guaranteed to be outside the range, making the traversal much faster on average. This can be implemented both recursively and iteratively.

#### Recursive Implementation
The recursive function returns the sum of the valid nodes in the subtree rooted at the current node.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }

        // If current node's value is too high, search only in the left subtree
        if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }

        // If current node's value is too low, search only in the right subtree
        if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }

        // If current node's value is in range, add it to the sum
        // and explore both subtrees for other possible values in range.
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }
}
```

#### Iterative Implementation (using a Stack for DFS)
This version avoids recursion, which can be beneficial for extremely deep trees to prevent stack overflow.
```java
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        if (root == null) {
            return sum;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                // If node is in range, add its value
                if (node.val >= low && node.val <= high) {
                    sum += node.val;
                }
                // If current node's value is greater than low, its left child might be in range
                if (node.val > low) {
                    stack.push(node.left);
                }
                // If current node's value is less than high, its right child might be in range
                if (node.val < high) {
                    stack.push(node.right);
                }
            }
        }
        return sum;
    }
}
```
### Algorithm
#### Recursive Approach:
1.  If the current `node` is null, return 0.
2.  If `node.val < low`, it means all values in the left subtree are also less than `low`. So, we only need to search in the right subtree. Return `rangeSumBST(node.right, low, high)`.
3.  If `node.val > high`, it means all values in the right subtree are also greater than `high`. So, we only need to search in the left subtree. Return `rangeSumBST(node.left, low, high)`.
4.  If `low <= node.val <= high`, the current node is in the range. Its value must be added to the sum. We still need to check both left and right subtrees for other valid nodes. Return `node.val + rangeSumBST(node.left, low, high) + rangeSumBST(node.right, low, high)`.

#### Iterative Approach (DFS with Stack):
1.  Initialize `sum = 0` and a `stack`. Push the `root` node.
2.  Loop while the `stack` is not empty.
3.  Pop a `node` from the stack.
4.  If the `node` is not null:
5.  If `node.val` is within `[low, high]`, add `node.val` to `sum`.
6.  If `node.val > low`, push the left child onto the stack (as it might be in range).
7.  If `node.val < high`, push the right child onto the stack (as it might be in range).
8.  After the loop, return `sum`.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int RangeSumBST ( TreeNode root , int low , int high ) { return dfs ( root , low , high ); } private int dfs ( TreeNode root , int low , int high ) { if ( root == null ) { return 0 ; } int x = root . val ; int ans = low <= x && x <= high ? x : 0 ; if ( x > low ) { ans += dfs ( root . left , low , high ); } if ( x < high ) { ans += dfs ( root . right , low , high ); } return ans ; } }
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int rangeSumBST ( TreeNode root , int low , int high ) { if ( root == null ) { return 0 ; } if ( low <= root . val && root . val <= high ) { return root . val + rangeSumBST ( root . left , low , high ) + rangeSumBST ( root . right , low , high ); } else if ( root . val < low ) { return rangeSumBST ( root . right , low , high ); } else { return rangeSumBST ( root . left , low , high ); } } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int rangeSumBST ( TreeNode * root , int low , int high ) { if ( root == nullptr ) return 0 ; if ( low <= root -> val && root -> val <= high ) { return root -> val + rangeSumBST ( root -> left , low , high ) + rangeSumBST ( root -> right , low , high ); } else if ( root -> val < low ) { return rangeSumBST ( root -> right , low , high ); } else { return rangeSumBST ( root -> left , low , high ); } } };
```

### Python

```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 : def search ( node ): if not node : return if low <= node . val <= high : self . ans += node . val search ( node . left ) search ( node . right ) elif node . val < low : search ( node . right ) elif node . val > high : search ( node . left ) self . ans = 0 search ( root ) return self . ans
```