## Leetcode938

## Question: Find the total sum of values falling within the range L and R,

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15

Output: 32

## Solution 1: Use depth first search to traverse all the nodes and add the node value if it is within the range – pre/post/in order does not matter

time complexiity: O(n)

space complexity: O(h) recursive stack which is also height of BST tree

runtime: 228 ms | faster than 66.46% submissions

memory: 20.9 MB | less than 100.00% submissions

1 | def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int: |

## Solution 2: Use a stack to iteratively traverse all the nodes, then add the node value to the total sum if it falls within the range

time complexiity: O(n)

space complexity: O(h)

runtime: 224 ms | faster than 76.05% submissions

memory: 21 MB | less than 100.00% submissions

1 | def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int: |

## The runtime and memory are not accurate,

but still interesting. I ran the faster-than-90% submissions code but it appeared as 70% on my results. Tested proven.