Range sum of a BST

Question

You're given a BST and low, high values. You need to return the sum of all nodes that are within this range, inclusive.

Here's the offered solution:

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(node):
            nonlocal ans
            if node:
                if low <= node.val <= high:
                    ans += node.val
                if low < node.val:
                    dfs(node.left)
                if node.val < high:
                    dfs(node.right)

        ans = 0
        dfs(root)
        return ans

What I don't understand is, if the range is inclusive, shouldn't it be <= and >= in the second and third if statements?

Answer 1

See, the low < node.val and high > node.val decides which direction the binary search should take (left and right respectively). The first check is to add the node to the sum.

These conditions (>/<) need not to be inclusive as is low/high is equal to node.val, it would be added to the sum in the first if check. The purpose of these conditions is to eliminate subtrees that don’t need to be searched because they can’t possibly contain values within the range [low, high].

I don't think if you add <= or >= in last two checks the result will change, but that would lead to unnecessary recursive calls.