- Published on
Range Sum of BST
- Authors
- Name
- Alex Noh
Introduction
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].
Solutions
1. Using DFS(Recursion)
This solution leverages the properties of the binary search tree (BST) to prune unnecessary branches and efficiently compute the sum.
main.py
def range_sum_of_bst(root: Optional[TreeNode], low: int, high: int) -> int:
def dfs(node: Optional[TreeNode]) -> int:
if node:
# If node's value is less than low, skip the left subtree
if node.val < low:
return dfs(node.right)
# If node's value is greater than high, skip the right subtree
elif high < node.val:
return dfs(node.left)
# If node's value is within the range, include it and continue with both subtrees
else:
return node.val + dfs(node.left) + dfs(node.right)
return 0
return dfs(root)
2. Using DFS(Stack)
This approach uses an iterative DFS with a stack to avoid recursion and efficiently traverse the tree.
main.py
def range_sum_of_bst(root: Optional[TreeNode], low: int, high: int) -> int:
total = 0
stack = [root]
while stack:
node = stack.pop()
if node:
if node.val < low:
stack.append(node.right)
elif high < node.val:
stack.append(node.left)
else:
total += node.val
stack.append(node.left)
stack.append(node.right)
return total
3. Using BFS(Queue)
This approach uses BFS technique with a queue to traverse the tree level by level.
main.py
def range_sum_of_bst(root: Optional[TreeNode], low: int, high: int) -> int:
total = 0
queue = collections.deque([root])
while queue:
node = queue.popleft()
if node:
if node.val < low:
queue.append(node.right)
elif high < node.val:
queue.append(node.left)
else:
total += node.val
queue.append(node.left)
queue.append(node.right)
return total