https://leetcode.com/problems/range-sum-of-bst

One way to solve this problem is just iterate over our tree and for each element check if it is range or not. However here we are given, that out tree is BST, that is left subtree is always lesser than node lesser than right subtree. So, let us modify classical dfs a bit, where we traverse only nodes we need:

  1. Check value node.val and if it is in our range, add it to global sum.
  2. We need to visit left subtree only if node.val > low, that is if node.val < low, it means, that all nodes in left subtree less than node.val, that is less than low as well.
  3. Similarly, we visit right subtree only if node.val < high.

Complexity: time complexity is O(n), where n is nubmer of nodes in our tree, space complexity potentially O(n) as well. We can impove our estimations a bit and say, that time and space is O(m), where m is number of nodes in our answer.

class Solution:
    def rangeSumBST(self, root, low, high):
        def dfs(node):
            if not node: return
            if low <= node.val <= high: self.out += node.val
            if node.val > low:  dfs(node.left)
            if node.val < high: dfs(node.right)
                
        self.out = 0
        dfs(root)
        return self.out

If you like the solution, you can upvote it on leetcode discussion section: Problem 0938