Range Sum of BST

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
2
3
4
5
6
7
8
9
def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
if not root:
return 0

leftSum = self.rangeSumBST(root.left, L, R) if root.val >= L else 0
rightSum = self.rangeSumBST(root.right, L, R) if root.val <= R else 0
currentSum = root.val if L <= root.val <= R else 0

return leftSum + rightSum + currentSum

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
stack = [root]
totalSum = 0

while stack:
node = stack.pop()

if node.val >= L and node.left:
stack.append(node.left)

if node.val <= R and node.right:
stack.append(node.right)

if L <= node.val <= R:
totalSum += node.val

return totalSum

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.