Range Sum of BST (Leetcode 938)

Technique: FAITH technique of Recursion

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

This below solution is the simple DFS approach. But, there is a better solution for this problem.

DFS Solution (Here, we will traverse all the tree and check if each node lies in the range):

class Solution:

    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
    
        global ans
        ans=0
        
        def fun(root,low,high):
            global ans
            if(root is None):
                return
            if(root.val>=low and root.val<=high):
                ans=ans+root.val
            fun(root.left,low,high)
            fun(root.right,low,high)
            
        fun(root,low,high)
        return ans

Optimal Solution (We will make use of the property of BST. If node.val is less than low, we need not traverse the node's left sub tree and if node.val is greater than high, we need not traverse the node's right sub tree)

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        
        self.ans=0
        def fun(root,low,high):
            if(root is None):
                return
            if(root.val>=low and root.val<=high):
                self.ans=self.ans+root.val
                print(root.val)
                fun(root.left,low,high)
                fun(root.right,low,high)
            elif(root.val<low):
                print(root.val)
                fun(root.right,low,high)
            elif(root.val>high):
                print(root.val)
                fun(root.left,low,high)
        fun(root,low,high)
        return self.ans