C++ EASY TO SOLVE || Detailed Explanation While Optimizing Approach
Intuition:\nActually the question is pretty straightforward ,Basically the question maker is asking us to  add all the numbers in a BST with a certain range giv
**Intuition:**\nActually the question is pretty straightforward ,Basically the question maker is asking us to  add all the numbers in a BST with a certain range given for numbers like say range is given as  [Low,High]=[2,7] then we need to add all the values in BST with the numbers satisfying this range. So major people who thought of a solution will be either using  recursion ,DFS or BFS.\n*Now, let\'s talk about approach*\n\n**Algorithm:**\nIn the following algorithm we will be discussing the solution of dfs approach .\n1. let` sumofRange` be a variable that will be our final result . After this let\'s declare a dfs helper function .\n2. The base case will be when the tree is empty so we return null\n3. we have to find the` sumofRange` so for that we need to add all the root values which satisfyes the condition that `node values should be more than low and less than high` .If this is true than add it to `sumofRange`\n4. After this let\'s dig the depth\'s of the tree i.e Left childs and Right childs.\n5. Now just call out the dfs helper function in the main function \n\n**Code:-**\n```\nclass Solution {\npublic:  \n    void dfs(TreeNode* root, int L, int R, int& sumOfRange){\n        if(!root) return;\n        if(root->val >= L && root->val <= R) sumOfRange += root->val;\n        if(root->val > L) dfs(root->left, L, R, sumOfRange);\n        if(root->val < R) dfs(root->right, L, R, sumOfRange);\n    }\n    \n    int rangeSumBST(TreeNode* root, int low, int high) {\n        int sumOfRange = 0;\n        dfs(root, low, high, sumOfRange);\n        return sumOfRange;\n    }\n};\n```\n**Time Complexity:** *`O(n) [n=number of nodes]`*\n**Space Complexity:** *`O(h) [h=height of tree] [Considering recursive calls]`*\n\n\n**Space Optimized Approach:**\nAfter exploring some other options, I found that we can actually optimize the space.\nThe logic is almost same as we discussed in the above approach .The main difference is that we use a stack for storing the data of nodes . So everytime we can just peek and pop the last values that we entered\n\n```\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        int sumofRange(0);\n        stack<TreeNode*> stack;\n        stack.push(root);\n        while(!stack.empty()){\n            TreeNode* node = stack.top(); stack.pop();\n            if(node->val>=L && node->val<=R) sumofRange+=node->val;\n            if(node->val > L) {if(node->left) stack.push(node->left);}\n            if(node->val < R) {if(node->right) stack.push(node->right);}\n        }\n        return sumofRange;\n    }\n};\n```\n\n**Time Complexity:** *`O(n) [n=number of nodes]`*\n**Space Complexity:** *`O(h) [h=height of the tree]`*\n
['Depth-First Search', 'Recursion', 'C', 'Binary Tree', 'C++']