7th December Daily Challenge LeetCode
Intuition\nMy Very First intuition to solve this approach was to traverse the tree in inorder manner, I did that and stored values of each Node in a seperate ar
# Intuition\nMy Very First intuition to solve this approach was to traverse the tree in inorder manner, I did that and stored values of each Node in a seperate array and then traversed the array to sum up values following the given constraints.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBut then I made a little change in the Inorder Traversal Algorithm and rather than to store in another array I updated the sums variable(variable storing my answer) at that place and then simply returned the sums variable storing my anser.\nNote: I defined a class variable sums to store my answer, so that I can update its value in a helper function findSum from inside the function.\n\nNote: The findSum function I used is simply a modified version of Inorder Traversal Function\n\nVote up if this Helps!\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity is same as that of inorder traversal, that is O(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nIf we consider the size of the stack for function calls then O(h + 1) and one is added for sums variable, where h is the height of the tree.\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n\n    sums = 0\n    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n        def findSum(root):\n            if root:\n                findSum(root.left)\n                if root.val <= high and root.val >= low:\n                    self.sums += root.val\n                findSum(root.right)\n        findSum(root)\n        \n        return self.sums\n\n```
['Binary Search Tree', 'Binary Tree', 'Python3']