Advertisement
kai-rocket

Range Sum of BST

Jul 15th, 2021
708
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.78 KB | None | 0 0
  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
  9.         # Base case, below leaf node, return 0
  10.         if not root:
  11.             return 0
  12.        
  13.         # Store subtree sums
  14.         subtree_sums = self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
  15.        
  16.         # Add the current node's value if the current node is within range
  17.         if root.val >= low and root.val <= high:
  18.             return subtree_sums + root.val
  19.        
  20.         # Return the range sum of the subtree rooted at the current node
  21.         return subtree_sums
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement