[C++] Recursive One-liner Solutions explained, ~100% Time, ~80% Space
This is a rather straightfoward problem and we might easily solve it calling a helper dfs function to gradually go top-down, from node to node, to solve it.\n\n
This is a rather straightfoward problem and we might easily solve it calling a helper `dfs` function to gradually go top-down, from node to node, to solve it.\n\nI preferred going for an extra bit of challenge and writing directly a recursive one-liner, ignoring the condition that it is a BST, since I found little value in potentially skipping a conditional every time we examine a node, whereas that would have costed much more code complexity.\n\nTo do so, I "hid" the result variable as a fourth optional parameter, defaulted to `0`.\n\nI will then return it when `root == NULL`, ie: we ended up out of the tree; otherwise, I will call recursively our `rangeSumBST` function on both the `left` and `right` branches, with a twist:\n* the call to the `left` branch will keep increasing `res` with the value of the current `root->val`;\n* the call to the `right` branch will every time reset `res` to `0` and compute a sub-sum from scratch.\n\nOnce all the recursive calls will be done, we I will have to just the result of `root->val` plus the sub-sum of everything to the left of it with the sub-sum of whatever is at the right of it :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int low, int high, int res = 0) {\n        return root ? rangeSumBST(root->left, low, high, res + (root->val >= low && root->val <= high ? root->val : 0)) + rangeSumBST(root->right, low, high) : res;\n    }\n};\n```\n\nAnd looking back to the one-liner I wrote in May, one that has some earlier stopping condition, I really struggle to find it worth in terms of extra performances, since it is one more check at each step.\n\nBasically at each iteration we update the upper and lower limit `low` and `high` as we go: going `left` will reduce potentially reduce `high`, while going `right` will have us check if we need to update `low`.\n\nAt the beginning of our code, we are not checking that `root` is not `NULL`, plus the new condition `low <= high`, meaning we already reached a part of the tree that does not matter to us.\n\nFor example, if we started with `low == 10` and `high == 20`, moving `left` after having it a node with value `9` or lower (and thus having updated `high` to that value) would not be meaningul, since by definition any value to its left needs to be smaller in a BST; similarly moving `right` after encountering anything `> 20` should have us halt right there.\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, int low, int high) {\n        return root && low <= high ? (root->val >= low && root->val <= high ? root->val : 0) + rangeSumBST(root->left, low, min(high, root->val)) + rangeSumBST(root->right, max(root->val, low), high) : 0;\n    }\n};\n```\n\nHybrid of the 2 approaches, using also [RedaKerouicha](https://leetcode.com/RedaKerouicha/)\'s suggestion:\n\n```cpp\nclass Solution {\npublic:\n    int rangeSumBST(TreeNode* root, const int low, const int high, const int res = 0) {\n        return root && low <= high ? rangeSumBST(root->left, low, min(high, root->val), res + (root->val >= low && root->val <= high ? root->val : 0)) + rangeSumBST(root->right, max(root->val, low), high) : res;\n    }\n};\n```
['Depth-First Search', 'Graph', 'C', 'C++']