✅ [C++/Python] Simple Solution w/ Explanation | DFS + BFS w/ Optimizations + O(1) Morris
We are given a BST and range [L, H]. We need to return sum of all nodes between this range.\n\n---\n\n\u2714\uFE0F Solution - I (Simple DFS)\n\nWe can perform a
We are given a BST and range `[L, H]`. We need to return sum of all nodes between this range.\n\n---\n\n\u2714\uFE0F ***Solution - I (Simple DFS)***\n\nWe can perform a simple DFS traversal over the tree and if the current node\'s value is within the range `[L, H]`, then we will add it to the final sum. The same process can be carried out recursively till whole tree is explored.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int H) {\n        if(!root) return 0;\n        return  (root -> val >= L && root -> val <= H ? root -> val : 0) +  // add root\'s value if it lies within [L, H]\n                rangeSumBST(root -> left, L, H) +   // recurse left\n                rangeSumBST(root -> right, L, H);   // recurse right\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def rangeSumBST(self, root, L, H):\n        if not root: return 0\n        return  (root.val if root.val >= L and root.val <= H else 0) + \\\n                self.rangeSumBST(root.left, L, H) + \\\n                self.rangeSumBST(root.right, L, H)\n```\n\n\n***Time Complexity :*** <code>O(N)</code>, where `N` is the number of nodes in the given tree\n***Space Complexity :*** `O(H)`, where `H` is the height of the tree. This is required for recursive stack. In case of skewed tree, this would be `O(N)`, while in case of balanced tree, this would be `O(logN)`\n\n---\n\n\u2714\uFE0F ***Solution - II (BST Optimized DFS)***\n\nIn the above solution, we aren\'t taking the advantage of the fact that our given tree is a BST. We can reduce the search space in some cases by doing conditional recursion. \n* If the root\'s value is less than `L`, then it\'s useless to further recurse the left sub-tree because we know that every node in left sub-tree will be less than `L` as well. **So iterate `root -> left` only when `root -> val > L`**\n* Similarly, if root\'s value is greater than `H`, we must not further recurse the right sub-tree. **So iterate `root -> right` only when `root -> val < H`**\n\nThe above two conditional checks help prune some recursive branches and thus optimize the solution slightly. Note that the time complexity still remains the same as the range can cover all nodes of BST.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int H) {\n        if(!root) return 0;\n        int ans = root -> val >= L && root -> val <= H ? root -> val : 0;\n        if(root -> val > L) ans += rangeSumBST(root -> left, L, H);\n        if(root -> val < H) ans += rangeSumBST(root -> right, L, H);\n        return ans;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def rangeSumBST(self, root, L, H):\n        if not root: return 0\n        ans = root.val if root.val >= L and root.val <= H else 0\n        if root.val > L: ans += self.rangeSumBST(root.left, L, H)\n        if root.val < H: ans += self.rangeSumBST(root.right, L, H)\n        return ans\n```\n\n***Time Complexity :*** <code>O(N)</code>, more specifically, this solution would only iterate the nodes which lie within the range `[L, H]`\n***Space Complexity :*** `O(H)`\n\n---\n\n\u2714\uFE0F ***Solution - III (BST Optimized BFS)***\n\nThe same thing can be done using BFS traversal as well. Similar to above approach, we will only push a left or right child into queue if the root\'s value is `> L` or `< H` respectively\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* T, int L, int H) {\n        queue<TreeNode*> q;\n        q.push(T);\n        int sum = 0, v;\n        while(size(q)) {\n            T = q.front(); q.pop();\n            v = T -> val;\n            if(v >= L and v <= H)   sum += v;\n            if(v > L && T -> left)  q.push(T -> left);\n            if(v < H && T -> right) q.push(T -> right);\n        }\n        return sum;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def rangeSumBST(self, T, L, H):\n        q, ans, v = deque([T]), 0, 0\n        while q:\n            T = q.popleft()\n            v = T.val\n            if v >= L and v <= H:  ans += v\n            if v > L and T.left:   q.append(T.left)\n            if v < H and T.right:  q.append(T.right)\n        return ans\n```\n\n***Time Complexity :*** <code>O(N)</code>\n***Space Complexity :*** `O(W)`, where `W` is the width of BST. In case of skewed tree, it will be `O(1)` and in case of balanced tree it will be `O(N/2) ~ O(N)`\n\n---\n\n\u2714\uFE0F ***Solution - IV (Morris Traversal)***\n\nWe can also use the Morris traversal (using the inorder version in this case) to optimze on space. I have also made some modification to prune further searches where we know that required node wont be found. You can read more on morris traversal **[here](https://leetcode.com/problems/binary-tree-inorder-traversal/solution/)** and **[here](https://stackoverflow.com/questions/5502916)**.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int H) {\n        int ans = 0;\n        while(root) \n            if(root -> left && root -> val >= L) {\n                auto pre = root -> left;  \n                // finding predecessor of root\n                while(pre -> right && pre -> val <= H) pre = pre -> right;\n                // make root as right child of predecessor (temporary link)\n                pre -> right = root;        // adding temporary link\n                auto tmp = root;\n                root = root -> left;                    \n                tmp -> left = nullptr;      // avoiding inifinte loop\n            }\n\t\t\telse {\n                if(root -> val >= L && root -> val <= H) ans += root -> val;\n                if(root -> val < H) root = root -> right;\n                else break;\n            }\n        \n        return ans;\n    }\n};\n```\n\nThe above version modifies the tree. The following can be used if tree modification is not allowed- \n\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int L, int H) {\n        int ans = 0;\n        while(root) \n            if(root -> left && root -> val >= L) {\n                auto pre = root -> left;  \n                // find predecessor of root\n                while(pre -> right && pre -> right != root)  pre = pre -> right;\n                // make root as right child of predecessor (temporary link)\n                if(!pre -> right) {\n                    pre -> right = root;\n                    root = root -> left;                    \n                }\n                else {                    \n                    if(root -> val >= L && root -> val <= H) ans += root -> val;\n                    pre -> right = nullptr;  // revert the changes - remove temporary link\n                    root = root -> right;\n                }\n            } \n\t\t\telse {\n                if(root -> val >= L && root -> val <= H) ans += root -> val;\n                root = root -> right;\n            }\n        \n        return ans;\n    }\n};\n```\n\nThe 1st version is optimized to prune redundant search wherever possible, but I guess the 2nd version only prunes left branches. If there\'s a more optimized version of morris traversal that restores the tree as well, do comment below...\n\n***Time Complexity :*** <code>O(N)</code>\n***Space Complexity :*** `O(1)`, only constant space is being used\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]