Python 🐍 | Easy Explanation | 2 Methods
\nPlatform: leetcode.com\n938. Range Sum of BST\nLink: https://leetcode.com/problems/range-sum-of-bst/\nDifficulty: Easy\nAuthor: hritik5102\nDate: 17/1/2021\nS
```\nPlatform: leetcode.com\n938. Range Sum of BST\nLink: https://leetcode.com/problems/range-sum-of-bst/\nDifficulty: Easy\nAuthor: hritik5102\nDate: 17/1/2021\nSubmission: https://leetcode.com/submissions/detail/444136335/\n(Time, Space) Complexity : O(n), O(H)\n\nRange sum of BST \n\n1.  We can solve this problem using recursion and iteration \n\niteration                                  Recursion \n1. implemented using loops                  1. implemented using function calls \n2. Defined by the control variable          2. Defined by the parameter value in the stack\nvalue  \n3. iteration makes size of Code            3. Recursion decreses the size of code\nbigger                                      \n4. Loop ends when control variable          4. Recursion ends when base case are True\nsatisfy the condition \n5. Infinite loops uses CPU Cycle            5. Infinite Recursion cause stack overflow at particular point or might crash the system\n6. Execution is faster                      6. Execution is slower\n```\n\n# Method 01 \n# Inorder traversal ( Left child , Node , Right child)\n\n**Disadvantage of using Inorder traversal method**\n\n1. Using this approach we are visiting at each node of the binary tree and we are not utilizing the benefit of binary tree.\n\n2. Time: O(n), space: O(h), where n is the number of total nodes, h is the height of the tree.\n\n\n```\nclass Solution:    \n    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n        output = []\n        if root==None:\n            return 0\n        self.inOrderTraversal(root,low,high,output)\n        return sum(output) \n    \n    def inOrderTraversal(self, root,low,high,output):\n        if root == None:\n            return\n\t\t\n\t\t# Left \n        self.inOrderTraversal(root.left, low,high,output)\n\t\t\n\t\t# Node \n        if low <= root.val <= high:\n            output.append(root.val)\n\t\t\t\n\t\t# Right\n        self.inOrderTraversal(root.right, low,high,output)\n\n```\n\nSo what we do when we search a particular number in a binary tree\n\nfirst we check if a number is less then a root, if yes then we search in left subtree else if it\'s greater then we search in right subtree of root node\n\nsame here, we see \n```\n1. if low < root :\n\t\t inOrderTraversal( root.left, low, high)\n\n2. if High > root :\n\t\t inOrderTraversal( root.right, low, high)     \n```\n\n# Method 02 \n```\nclass Solution:    \n    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n        output = []\n        if root==None:\n            return 0\n        self.inOrderTraversal(root,low,high,output)\n        return sum(output) \n    \n    def inOrderTraversal(self, root,low,high,output):\n        if root == None:\n            return\n\t\t\t\n\t\t# left \n        if low<root.val:\n            self.inOrderTraversal(root.left, low,high,output)\n\t\t\n\t\t# Node\n        if low <= root.val <= high:\n            output.append(root.val)\n\t\t\n\t\t# RIght \n        if high>root.val:\n            self.inOrderTraversal(root.right, low,high,output)\n```\n\n# Method 03 \n## Same Logic but reduction in line of code\n```\nclass Solution:    \n    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n        total = 0\n        if root==None:\n            return 0\n        if low <= root.val <= high:\n            total +=root.val\n        if low<root.val:\n            total += self.rangeSumBST(root.left, low,high)\n        if high>root.val:\n            total += self.rangeSumBST(root.right, low,high)\n        \n        return total \n```\n\n        \n
['Python']