aboutsummaryrefslogtreecommitdiff
path: root/range_sum_bst.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /range_sum_bst.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'range_sum_bst.py')
-rw-r--r--range_sum_bst.py41
1 files changed, 41 insertions, 0 deletions
diff --git a/range_sum_bst.py b/range_sum_bst.py
new file mode 100644
index 0000000..f783759
--- /dev/null
+++ b/range_sum_bst.py
@@ -0,0 +1,41 @@
+# 938. Range Sum of BST
+
+"""
+given the 'root' 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)'
+"""
+
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+class Solution(object):
+ def rangeSumBST(self, root, low, high):
+ """
+ :type root: TreeNode
+ :type low: int
+ :type high: int
+ :rtype: int
+ """
+ def dfs(node):
+ if not node:
+ return 0
+
+ current_val = 0
+ if low <= node.val <= high:
+ current_val = node.val
+
+ left_sum = dfs(node.left)
+ right_sum = dfs(node.right)
+
+ return current_val + left_sum + right_sum
+
+ return dfs(root)
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.rangeSumBST(root = [10,5,15,3,7,null,18], low = 7, high = 15)) # expect: 15
+ print(obj.rangeSumBST(root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10)) # expect: 23