~100.00% fast in memory and run-time dfs - recursive/iterative solution
Compare yourself, as the different ways are below: satisfied? \nDon\'t look at runtime, as this may change time to time on each submission. Have a look at optim
Compare yourself, as the different ways are below: satisfied? \nDon\'t look at runtime, as this may change time to time on each submission. Have a look at optimized approach.\n\n-------\nRuntime: 84 ms, faster than 98.75% of C++ online submissions for Range Sum of BST.\nMemory Usage: 41.1 MB, less than 99.09% of C++ online submissions for Range Sum of BST.\nIf root\'s value is greater than L then move left, and if it\'s value if less than R then move right.\nTime Complexity: **O(N)**, where N is the number of nodes in the tree.\nSpace Complexity: **O(H)**, where H is the height of the tree. i.e. **O(1)**\n```\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        int rangeSum(0);\n        stack<TreeNode*> st;\n        st.push(root);\n        while(!st.empty()){\n            TreeNode* node = st.top(); st.pop();\n            if(node->val>=L && node->val<=R) rangeSum+=node->val;\n            if(node->val > L) {if(node->left) st.push(node->left);}\n            if(node->val < R) {if(node->right) st.push(node->right);}\n        }\n        return rangeSum;\n    }\n};\n```\n\n---------------\nTime Complexity **O(n)** & Space Complexity **O(n)**\nRuntime: 96 ms, faster than 95.88% of C++ online submissions for Range Sum of BST.\nMemory Usage: 41.1 MB, less than 100.00% of C++ online submissions for Range Sum of BST.\n```\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        if(!root) return 0;\n        return ((root->val>=L && root->val<=R)? root->val : 0) + rangeSumBST(root->left,L,R) + rangeSumBST(root->right,L,R);\n    }\n};\n```\n\n---------------\nRuntime: 80 ms, faster than 92.88% of C++ online submissions for Range Sum of BST.\nMemory Usage: 41.2 MB, less than 100.00% of C++ online submissions for Range Sum of BST.\n\n```\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        if(!root) return 0;\n    return ((root->val>=L && root->val<=R)? (root->val + rangeSumBST(root->left,L,R) + rangeSumBST(root->right,L,R)) : (root->val<L)? rangeSumBST(root->right,L,R): rangeSumBST(root->left,L,R));\n    }\n};\n```\n\n--------------\nRuntime: 92 ms, faster than 96.85% of C++ online submissions for Range Sum of BST.\nMemory Usage: 41.2 MB, less than 89.09% of C++ online submissions for Range Sum of BST.\n```\nclass Solution {\npublic:\n    int helper(TreeNode* root, int L, int R, int rangeSum){\n        if(!root) return 0;\n        else if(root->val>=L && root->val<=R){\n            rangeSum+=helper(root->left,L,R,0);\n            rangeSum+=helper(root->right,L,R,0);\n            return rangeSum + root->val;\n        }else if(root->val > L){\n            rangeSum+=helper(root->left,L,R,0);\n            return rangeSum;\n        }else if(root->val < R){\n            rangeSum+=helper(root->right,L,R,0);\n            return rangeSum;\n        }\n        return 0;\n    }\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        std::ios::sync_with_stdio(false);\n        return helper(root,L,R,0);\n    }\n};\n```\n\n-----------------\nRuntime: 92 ms, faster than 96.92% of C++ online submissions for Range Sum of BST.\nMemory Usage: 41.2 MB, less than 86.36% of C++ online submissions for Range Sum of BST.\nSolution: **We traverse the tree using a depth first search. If node.val falls outside the range [L, R], (for example node.val < L), then we know that only the right branch could have nodes with value inside [L, R].**\nTC: **O(n)**, SC: **O(n)**\n```\nclass Solution { // dfs\nprivate:\n    int rangeSum;\npublic:\n    void dfs(TreeNode* root, int L, int R){\n        if(!root) return;\n        if(root->val>=L && root->val<=R) rangeSum+=root->val;\n        if(root->val > L) dfs(root->left,L,R);\n        if(root->val < R) dfs(root->right,L,R);\n    }\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        rangeSum = 0;\n        dfs(root,L,R);\n        return rangeSum;\n    }\n};\n```\n\n----------------------\nRuntime: 148 ms, faster than 76.44% of C++ online submissions for Range Sum of BST.\nMemory Usage: 41.2 MB, less than 88.18% of C++ online submissions for Range Sum of BST.\n\n```\nclass Solution {\npublic:\n    void dfs(TreeNode* root, int &rangeSum, int L, int R, bool isDone){\n        if(!root || isDone) return;\n        dfs(root->left,rangeSum,L,R,false);\n        if(root->val>=L && root->val<=R){\n            rangeSum+=root->val;\n            if(root->val==R) isDone = true;\n        }\n        dfs(root->right,rangeSum,L,R,false);\n    }\n    int rangeSumBST(TreeNode* root, int L, int R) {\n        int rangeSum(0);\n        dfs(root,rangeSum,L,R,false);\n        return rangeSum;\n    }\n};\n```\n\n--------\n\n
['Depth-First Search', 'Recursion', 'C', 'Iterator', 'C++']