Beats 99.98% Users - C++, JAVA, Python, JavaScript || With explanation ||
\n---\n\n\n\n---\n\n\n# Approach\n Describe your approach to solving the problem. \n\n1. Iterative In-Order Traversal:\n  - The code uses a modified in-order tr
\n---\n\n![Screenshot 2024-01-08 075029.png](https://assets.leetcode.com/users/images/bbeb486c-d103-43ca-beb2-565072b00024_1704680445.9386897.png)\n\n---\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n**1. Iterative In-Order Traversal:**\n  - The code uses a modified in-order traversal to visit nodes in ascending order without using recursion.\n  - It achieves this by temporarily linking rightmost nodes of left subtrees to their parents, creating a kind of threaded binary tree.\n\n**2. Range Check and Sum Addition:**\n  - For each visited node, its value is checked against the `low` and `high` range:\n     - If it falls within the range, its value is added to the `sum` variable.\n\n**3. Right Subtree Exploration:**\n  - After processing a node, the traversal continues to its right subtree to explore values that might also fall within the range.\n\n**4. Temporary Link Removal:**\n  - The temporary links created during the traversal are removed to restore the original tree structure.\n\n**5. Final Sum:**\n  - The function returns the `sum` variable, which holds the accumulated value of all nodes within the specified range.\n\n**Time Complexity:**\n  - O(N)\n    - The traversal visits each node in the BST exactly once, leading to linear time complexity.\n\n**Space Complexity:**\n  - O(1)\n    - The space used for variables remains constant, independent of the BST size.\n    - The temporary link manipulation doesn\'t require additional space in terms of asymptotic complexity.\n\n\n# Code\n```C++ []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\n\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int low, int high) {\n        int sum=0;\n        while(root){\n            if(root->left){\n                TreeNode* temp=root->left;\n                TreeNode* curr=root->left;\n                while(temp->right){\n                    temp=temp->right;\n                }\n                temp->right=root;\n                root->left=NULL;\n                root=curr;\n            }\n            else{\n                if(root->val>=low&&root->val<=high){\n                    sum+=root->val;\n                }\n                root=root->right;\n            }\n        }\n        return sum;\n    }\n};\n```\n```java []\nclass Solution {\n    public int rangeSumBST(TreeNode root, int low, int high) {\n        int sum = 0;\n        while (root != null) {\n            if (root.left != null) {\n                TreeNode temp = root.left;\n                while (temp.right != null && temp.right != root) {\n                    temp = temp.right;\n                }\n                if (temp.right == null) {\n                    temp.right = root;\n                    root = root.left;\n                } else {\n                    temp.right = null;\n                }\n            } else {\n                if (root.val >= low && root.val <= high) {\n                    sum += root.val;\n                }\n                root = root.right;\n            }\n        }\n        return sum;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n        sum = 0\n        node = root\n        while node:\n            if node.left:\n                prev = node.left\n                while prev.right and prev.right != node:\n                    prev = prev.right\n                if not prev.right:\n                    prev.right = node\n                    node = node.left\n                else:\n                    prev.right = None\n            elif low <= node.val <= high:\n                sum += node.val\n            node = node.right\n        return sum\n\n```\n```javascript []\nclass Solution {\n    rangeSumBST(root, low, high) {\n        let sum = 0;\n        let node = root;\n        while (node) {\n            if (node.left) {\n                let prev = node.left;\n                while (prev.right && prev.right !== node) {\n                    prev = prev.right;\n                }\n                if (!prev.right) {\n                    prev.right = node;\n                    node = node.left;\n                } else {\n                    prev.right = null;\n                }\n            } else {\n                if (low <= node.val && node.val <= high) {\n                    sum += node.val;\n                }\n                node = node.right;\n            }\n        }\n        return sum;\n    }\n}\n\n```\n\n
['Binary Search Tree', 'Binary Tree', 'Python', 'C++', 'Java', 'JavaScript']