938. Range Sum of BST
https://leetcode.com/problems/range-sum-of-bst/
Given the
root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
The binary search tree is guaranteed to have unique values.
Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15 Output: 32
Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10 Output: 23
Note:
- The number of nodes in the tree is at most
10000. - The final answer is guaranteed to be less than
2^31.
---
Intuition
We need to cover all nodes - simple dfs with check at each node is trivial - O(n)
We can use the info that this is BST
If current node val >=L => dfs (node.left)
if current node val <= R => dfs (node.right)
---
Time - O(R - L) ~ O(N)
Space - O(1)
---
