Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].
Bruteforce Algorithm to Compute the Range Sum of a BST
We can bruteforce all the nodes and then add the answer only if the node falls in the range. The time complexity is O(N) as we need to visit N nodes exactly.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int: if not root: return 0 ans = 0 if root.val >= low and root.val <= high: ans += root.val ans += self.rangeSumBST(root.left, low, high) ans += self.rangeSumBST(root.right, low, high) return ans |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int: if not root: return 0 ans = 0 if root.val >= low and root.val <= high: ans += root.val ans += self.rangeSumBST(root.left, low, high) ans += self.rangeSumBST(root.right, low, high) return ans
Recursive Depth First Search Algorithm to Compute the Range Sum of a BST
Based on above bruteforce algorithm, we can abandon half of the branch if the current value is outside the valid range. The time complexity is O(H) where H is the height of the BST – and H = Log(N) for a balanced binary search tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int: if not root: return 0 ans = 0 if root.val >= low and root.val <= high: ans += root.val if root.val > low: ans += self.rangeSumBST(root.left, low, high) if root.val < high: ans += self.rangeSumBST(root.right, low, high) return ans |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int: if not root: return 0 ans = 0 if root.val >= low and root.val <= high: ans += root.val if root.val > low: ans += self.rangeSumBST(root.left, low, high) if root.val < high: ans += self.rangeSumBST(root.right, low, high) return ans
Iterative Depth First Search Algorithm to Compute the Range Sum of a BST
We can also use the stack to perform the DFS in order to compute the range sum of a Binary Search Tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int: if not root: return 0 ans = 0 stack = [root] while stack: node = stack.pop() if node: if L <= node.val <= R: ans += node.val if L < node.val: stack.append(node.left) if node.val < R: stack.append(node.right) return ans |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int: if not root: return 0 ans = 0 stack = [root] while stack: node = stack.pop() if node: if L <= node.val <= R: ans += node.val if L < node.val: stack.append(node.left) if node.val < R: stack.append(node.right) return ans
See also other implementations of the Range Sum of BST in other programming languages:
– Teaching Kids Programming – Algorithms to Compute the Range Sum of a Binary Search Tree
– How to Sum within A Range in a Binary Search Tree?
– GoLang: Algorithm to Compute the Range Sum of a Binary Search Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Remove Vowels from a String
Next Post: How to Get Number of CPU Cores using PHP Function (Platform Independent)