---
# System prepended metadata

title: '[938. Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/description/)'
tags: [Binary Search Tree, easy, Tree, leetcode, Depth-First Search, Binary Tree]

---

###### tags: `leetcode` `easy` `Tree` `Depth-First Search` `Binary Search Tree` `Binary Tree`
# [938. Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/description/)

## Description

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]`.  

## Examples
### Example 1:

![bst1](https://assets.leetcode.com/uploads/2020/11/05/bst1.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:

![bst2](https://assets.leetcode.com/uploads/2020/11/05/bst2.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 \leq Node.val \leq 10^5$  
- $1 \leq low \leq high \leq 10^5$  
- All `Node.val` are **unique**.  

## Code

- Type 1
```c=
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int rangeSumBST(struct TreeNode* root, int low, int high) {
    if (!root)
        return 0;
    return (((root->val >= low) && (root->val <= high)) ? root->val : 0) +
           ((root->right) ? rangeSumBST(root->right, low, high) : 0) +
           ((root->left) ? rangeSumBST(root->left, low, high) : 0);
}
```

- Type 2
```c=
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int rangeSumBST(struct TreeNode* root, int low, int high) {
    if (!root)
        return 0;
    if (root->right) {
        if (root->left) {
            return (((root->val >= low) && (root->val <= high)) ? root->val : 0) +
                rangeSumBST(root->right, low, high) +
                rangeSumBST(root->left, low, high);
        }
        return (((root->val >= low) && (root->val <= high)) ? root->val : 0) +
            rangeSumBST(root->right, low, high);
    }
    if (root->left) {
        return (((root->val >= low) && (root->val <= high)) ? root->val : 0) +
            rangeSumBST(root->left, low, high);
    }
    return (((root->val >= low) && (root->val <= high)) ? root->val : 0);
}
```

- Type 3
```c=
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int rangeSumBST(struct TreeNode* root, int low, int high){
    if(!root) return 0;
    int result = 0;
    result += ((root->val >= low) && (root->val <= high)) ? root->val : 0;
    if(root->left) result += rangeSumBST(root->left, low, high);
    if(root->right) result += rangeSumBST(root->right, low, high);
    return result;
}
```

## Complexity

|Space |Time  |
|-     |-     |
|$O(1)$|$O(N)$|

## Result

- Type 1 :
    - Runtime : 94 ms, 89.94%  
    - Memory : 42.4 MB, 43.58%  
- Type 2 :
    - Runtime : 93 ms, 92.74%  
    - Memory : 42.5 MB, 21.23%  
- Type 3 :
    - Runtime : 91 ms, 94.41%  
    - Memory : 42.4 MB, 58.66%