Daily Coding Problem #1511

Good morning! Here’s your coding interview problem for today.

This problem was asked by Google.

Given a binary search tree and a range [a, b] (inclusive), return the sum of the elements of the binary search tree within the range.

For example, given the following tree:

    5
   / \
  3   8
 / \ / \
2  4 6  10

and the range [4, 9], return 23 (5 + 4 + 6 + 8).

The problem is also the same as LeetCode 938 and this problem has not only been asked by google but also by meta, and a lot recently.

The way to approach this problem is to do a pre-order traversal and at each step check whether the value at the node is within the specified range, if it is then we add it to our running sum.

Now when do you want to go to the left node, it’s only when the value of your node is greater than the lower bound. If the value of your node is lesser than the lower bound, then you don’t want to explore the left sub-tree as all of them will have value lower than the node.

Again, you only want to explore the right subtree if the value of the current node is less than the upper bound.

So we call the function recursively on the left subtree if the value of the current node is higher than the lower bound and on the right subtree if the value of the node is lower than the upper bound.

Here is the solution –

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0

        self.range_sum = 0
        self.dfs(root,low,high)
        return self.range_sum

    def dfs(self,node,low,high):
        if not node:
            return 0

        if low <=node.val<=high:
            self.range_sum+=node.val
        
        if node.val > low:
            self.dfs(node.left,low,high)

        if node.val < high:
            self.dfs(node.right,low,high)

Both time and space complexity is O(N) cause we are exploring all the nodes in the worse case and the recursive call stack takes up O(N) space.