Easy Processes🔥| Completely Optimised✔| C++✔|Java✔|Python✔|
Approach 1 - In-order Traversal with Stack\n# Intuition\nThe goal is to find the sum of values within a given range in a Binary Search Tree (BST). A stack-based
# Approach 1 - In-order Traversal with Stack\n# Intuition\nThe goal is to find the sum of values within a given range in a Binary Search Tree (BST). A stack-based iterative approach can efficiently traverse the BST.\n\n# Approach\nWe use a stack to perform an in-order traversal of the BST. At each step, we check if the current node\'s value falls within the specified range [L, R]. If yes, we add it to the sum. We then move to the right subtree if it exists, as we are traversing in-order.\n\n# Complexity\n- Time complexity:O(n)\n    - Each node is visited once, where n is the number of nodes in the BST.\n\n- Space complexity:O(h)\n    - The space required by the stack is proportional to the height of the BST. In the worst case, when the BST is skewed, it is O(n), but in a balanced BST, it is O(log n).\n\n# C++ Code\n```\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        int sum = 0;\n        stack<TreeNode*> stk;\n\n        while (root != nullptr || !stk.empty()) {\n            while (root != nullptr) {\n                stk.push(root);\n                root = root->left;\n            }\n\n            root = stk.top();\n            stk.pop();\n\n            if (root->val >= L && root->val <= R) {\n                sum += root->val;\n            }\n\n            root = root->right;\n        }\n\n        return sum;\n    }\n};\n\n```\n# Java\n```\nimport java.util.Stack;\n\nclass Solution {\n    public int rangeSumBST(TreeNode root, int L, int R) {\n        int sum = 0;\n        Stack<TreeNode> stack = new Stack<>();\n\n        while (root != null || !stack.isEmpty()) {\n            while (root != null) {\n                stack.push(root);\n                root = root.left;\n            }\n\n            root = stack.pop();\n\n            if (root.val >= L && root.val <= R) {\n                sum += root.val;\n            }\n\n            root = root.right;\n        }\n\n        return sum;\n    }\n}\n\n```\n# Python \n```\nclass Solution:\n    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n        sum_val = 0\n        stack = []\n\n        while root or stack:\n            while root:\n                stack.append(root)\n                root = root.left\n\n            root = stack.pop()\n\n            if L <= root.val <= R:\n                sum_val += root.val\n\n            root = root.right\n\n        return sum_val\n\n```\n\n---\n\n# Approach 2 - Recursive Range Sum\n# Approach\n\n1. Check if the current node is null or the range [L, R] is invalid (L > R), return 0 in such cases.\n2. Compare the value of the current node with L and R.\n    - If the value is less than L, explore the right subtree.\n    - If the value is greater than R, explore the left subtree.\n    - If the value is within the range [L, R], include the current node\'s value in the sum.\n3. Recursively explore both left and right subtrees.\n4. Return the sum of values within the specified range.\n\n# Time Complexity - O(n)\n# Space Complexity - O(H)\n\n# C++ Code\n ```\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        if (!root) return 0;\n\n        if (root->val < L)\n            return rangeSumBST(root->right, L, R);\n\n        if (root->val > R)\n            return rangeSumBST(root->left, L, R);\n\n        return root->val + rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R);\n    }\n};\n\n```\n# Java\n```\npublic class Solution {\n    public int rangeSumBST(TreeNode root, int L, int R) {\n        if (root == null || L > R) {\n            return 0;\n        }\n\n        if (root.val < L) {\n            return rangeSumBST(root.right, L, R);\n        }\n\n        if (root.val > R) {\n            return rangeSumBST(root.left, L, R);\n        }\n\n        return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);\n    }\n}\n```\n# Python \n```\nclass Solution:\n    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n        if not root or L > R:\n            return 0\n\n        if root.val < L:\n            return self.rangeSumBST(root.right, L, R)\n\n        if root.val > R:\n            return self.rangeSumBST(root.left, L, R)\n\n        return root.val + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R)\n\n```\n
['Tree', 'Depth-First Search', 'Binary Search Tree', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3']