C++/Python binary search Tree|69 ms Beats 99.46%
Intuition\n Describe your first thoughts on how to solve this problem. \nUse preOrder to solve.\n2nd approach uses postOrder.\n3rd approach uses inOrder, note t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse preOrder to solve.\n2nd approach uses postOrder.\n3rd approach uses inOrder, note that inOrder traversal is a way of sorting.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThis is a binary Search Tree problem. If you understand how to build the binary search tree, you can solve it.\n\n[Please turn on English subtitles if necessary]\n[https://youtu.be/KHVXYo7LxZE?si=2AU_RCL8SHq5WR0R](https://youtu.be/KHVXYo7LxZE?si=2AU_RCL8SHq5WR0R)\n\nAll testcases are expressed in their array representations.\nThe value for root is always on the head.\nInsert a node with value x in this BST, how to do it?\n- Loop: check whether `x>node->val`\nif yes, the node with value x must be in right subtree; let\n`node=node->right` , if `!node` insert here.\notherwise this node is in the left subtree; let\n`node=node->left` , if `!node` insert here.\n\nUse preOrder traversal can do the job; other traversals, eq. postOrder, inOrder, can do also. `rangeSumBST` can be implemented in the similar way.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nsystem stack + $$O(1)$$\n# Code 83 ms Beats 95.10%\n```\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 #pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int sum=0;\n    void preOrder(TreeNode* root, int low, int high){\n        if (!root) return ;\n        if (root->val<=high && root->val>=low) \n            sum+=root->val;\n        preOrder(root->left, low, high);\n        preOrder(root->right, low, high);\n    }\n    int rangeSumBST(TreeNode* root, int low, int high) {\n        preOrder(root, low, high);\n        return sum;  \n    }\n};\n\n```\n# Python Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n        ans=0\n        def preOrder(root, low, high):\n            nonlocal ans\n            if not root: return\n            if low<=root.val<=high:\n                ans+=root.val\n            preOrder(root.left, low, high)\n            preOrder(root.right, low, high)\n        \n        preOrder(root, low, high)\n        return ans\n        \n```\n# C++ using postOrder||75 ms Beats 98.41%\n```\n    int sum=0;\n    void postOrder(TreeNode* root, int low, int high){\n        if (!root) return ;\n        postOrder(root->left, low, high);\n        postOrder(root->right, low, high);\n        if (root->val<=high && root->val>=low) \n            sum+=root->val;\n    }\n    int rangeSumBST(TreeNode* root, int low, int high) {\n        postOrder(root, low, high);\n        return sum;  \n    }\n```\n# C++ using Inorder||69 ms Beats 99.46%\n```\n    int sum=0;\n    void inOrder(TreeNode* root, int low, int high){\n        if (!root) return ;\n        int x=move(root->val);\n        if (x>high) inOrder(root->left, low, high);\n        else if (x<=high && x>=low){ \n            inOrder(root->left, low, high);\n            sum+=x;\n            inOrder(root->right, low, high);\n        }\n        else inOrder(root->right, low, high);\n    }\n    int rangeSumBST(TreeNode* root, int low, int high) {\n        inOrder(root, low, high);\n        return sum;  \n    }\n```
['Binary Search Tree', 'C++', 'Python3']