# Leetcode - 938. Range Sum of BST

## 풀이

쉽게 풀 수 있지만 BST의 특징을 활용하면 pruning이 가능하다.

class Solution:
cur_sum = 0

def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
def get_sum(node):
if not node:
return 0

get_sum(node.left)
get_sum(node.right)
if low <= node.val <= high:
self.cur_sum += node.val

get_sum(root)
return self.cur_sum

### DFS with pruning

class Solution:
cur_sum = 0

def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
def get_sum(node):
if node:

if node.val > high:
get_sum(node.left)
elif node.val < low:
get_sum(node.right)
else:
get_sum(node.left)
get_sum(node.right)

if low <= node.val <= high:
self.cur_sum += node.val

get_sum(root)
return self.cur_sum

### DFS with pruning 2

class Solution:
cur_sum = 0

def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
stack = [root]
cur_sum = 0

while stack:
node = stack.pop()
if not node:
continue

if node.val > low:
stack.append(node.left)
if node.val < high:
stack.append(node.right)

if low <= node.val <= high:
cur_sum += node.val

return cur_sum

### BFS with pruning

class Solution:
cur_sum = 0

def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
queue = [root]
cur_sum = 0

while queue:
node = queue.pop()
if not node:
continue

if node.val > low:
queue.append(node.left)
if node.val < high:
queue.append(node.right)

if low <= node.val <= high:
cur_sum += node.val

return cur_sum