range_sum_of_bst
1from typing import Optional 2from utils import TreeNode, to_bst 3 4# @leet start 5class Solution: 6 def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int: 7 """ 8 This function calculates the range sum of a BST between two numbers, `low` and `high`, inclusive. 9 To do this, imagine we have a tree node. There are two cases: 10 1. The node is null. In this case, we return 0. 11 2. The node is non-null. 12 In the non-null case, there are three cases: 13 1. If the node's value is within low..high. 14 a. In this case, we add the node's total to the sum and recurse to 15 the left and right nodes, since they both can also be in range. 16 2. If the node's value is $\lt$ low. 17 a. In this case, we know that the left node will always be less than the current node value. 18 Thus, we only want to check to the right. We do not add our current value to the sum, and 19 continue to recurse to the right hand side. 20 3. If the node's value is $\gt$ high. 21 a. In this case, we know the right node value is too high. Thus, we only check to the left. 22 We do not add our current value to the total, and only recurse to the left hand side, 23 since that would lower the next node's value. 24 """ 25 if not root: 26 return 0 27 if low <= root.val <= high: 28 return root.val + \ 29 self.rangeSumBST(root.left, low, high) + \ 30 self.rangeSumBST(root.right, low, high) 31 elif root.val > high: 32 return self.rangeSumBST(root.left, low, high) 33 elif root.val < low: 34 return self.rangeSumBST(root.right, low, high) 35 raise RuntimeError("This should be unreachable") 36 37 38# @leet end 39sol = Solution() 40def test(): 41 assert(sol.rangeSumBST(to_bst([10,5,15,3,7,None,18]), 7, 15) == 32) 42 assert(sol.rangeSumBST(to_bst([10,5,15,3,7,13,18,1,None,6]), 6, 10) == 23)
class
Solution:
6class Solution: 7 def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int: 8 """ 9 This function calculates the range sum of a BST between two numbers, `low` and `high`, inclusive. 10 To do this, imagine we have a tree node. There are two cases: 11 1. The node is null. In this case, we return 0. 12 2. The node is non-null. 13 In the non-null case, there are three cases: 14 1. If the node's value is within low..high. 15 a. In this case, we add the node's total to the sum and recurse to 16 the left and right nodes, since they both can also be in range. 17 2. If the node's value is $\lt$ low. 18 a. In this case, we know that the left node will always be less than the current node value. 19 Thus, we only want to check to the right. We do not add our current value to the sum, and 20 continue to recurse to the right hand side. 21 3. If the node's value is $\gt$ high. 22 a. In this case, we know the right node value is too high. Thus, we only check to the left. 23 We do not add our current value to the total, and only recurse to the left hand side, 24 since that would lower the next node's value. 25 """ 26 if not root: 27 return 0 28 if low <= root.val <= high: 29 return root.val + \ 30 self.rangeSumBST(root.left, low, high) + \ 31 self.rangeSumBST(root.right, low, high) 32 elif root.val > high: 33 return self.rangeSumBST(root.left, low, high) 34 elif root.val < low: 35 return self.rangeSumBST(root.right, low, high) 36 raise RuntimeError("This should be unreachable")
7 def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int: 8 """ 9 This function calculates the range sum of a BST between two numbers, `low` and `high`, inclusive. 10 To do this, imagine we have a tree node. There are two cases: 11 1. The node is null. In this case, we return 0. 12 2. The node is non-null. 13 In the non-null case, there are three cases: 14 1. If the node's value is within low..high. 15 a. In this case, we add the node's total to the sum and recurse to 16 the left and right nodes, since they both can also be in range. 17 2. If the node's value is $\lt$ low. 18 a. In this case, we know that the left node will always be less than the current node value. 19 Thus, we only want to check to the right. We do not add our current value to the sum, and 20 continue to recurse to the right hand side. 21 3. If the node's value is $\gt$ high. 22 a. In this case, we know the right node value is too high. Thus, we only check to the left. 23 We do not add our current value to the total, and only recurse to the left hand side, 24 since that would lower the next node's value. 25 """ 26 if not root: 27 return 0 28 if low <= root.val <= high: 29 return root.val + \ 30 self.rangeSumBST(root.left, low, high) + \ 31 self.rangeSumBST(root.right, low, high) 32 elif root.val > high: 33 return self.rangeSumBST(root.left, low, high) 34 elif root.val < low: 35 return self.rangeSumBST(root.right, low, high) 36 raise RuntimeError("This should be unreachable")
This function calculates the range sum of a BST between two numbers, low and high, inclusive.
To do this, imagine we have a tree node. There are two cases:
- The node is null. In this case, we return 0.
- The node is non-null. In the non-null case, there are three cases:
- If the node's value is within low..high. a. In this case, we add the node's total to the sum and recurse to the left and right nodes, since they both can also be in range.
- If the node's value is $\lt$ low. a. In this case, we know that the left node will always be less than the current node value. Thus, we only want to check to the right. We do not add our current value to the sum, and continue to recurse to the right hand side.
- If the node's value is $\gt$ high. a. In this case, we know the right node value is too high. Thus, we only check to the left. We do not add our current value to the total, and only recurse to the left hand side, since that would lower the next node's value.
sol =
<Solution object>
def
test():