✅ [Python/C++/Java] DFS & BFS & binary search (explained) + BONUS ONE-LINER
\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.\n*\nThis solution employs conditional traversal of a Binary Search Tree. Time complexity is linear: *O(N). Spac
**\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.**\n****\nThis solution employs conditional traversal of a Binary Search Tree. Time complexity is linear: **O(N)**. Space complexity is logarithmic (for a balanced tree): **O(logN)**.\n****\n\n**Comment.** Binary Search Tree (BST) is a type of binary tree for which the left (right) subtree of each node is also a BST with all values being less (greater) than the node\'s value. This defines a recursive strategy to compute range sums, namely:\n1. Take node\'s value if it\'s in range. \n2. If node\'s value is greater than the lower bound then search for valid values in the left subtree.\n3. If node\'s value is less than the upper bound then search for valid values in the right subtree.\n\n**Python #1.** DFS.\n```\nclass Solution:\n    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n        \n        if not root : return 0\n        \n        s = root.val if low <= root.val <= high else 0\n        if low  <= root.val : s += self.rangeSumBST(root.left,  low, high)\n        if high >= root.val : s += self.rangeSumBST(root.right, low, high)\n        \n        return s\n```\n\n**Python #2.** BFS.\n```\nclass Solution:\n    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n        dq, s = deque([root]), 0\n        while dq:\n            node = dq.popleft()\n            if low  <= node.val <= high        : s += node.val\n            if low  <= node.val and node.left  : dq.append(node.left)\n            if high >= node.val and node.right : dq.append(node.right)\n        return s\n```\n\nThere is also a more expensive, however, interesting approach. \n\n**Python #3.** Collect values in order then binary search.\n```\nclass Solution:\n    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n        \n        def inorder(n, v):\n            if n: inorder(n.left, v), v.append(n.val), inorder(n.right, v)\n        \n        vals = []\n        inorder(root, vals)\n        \n        return sum(vals[bisect_left(vals, low) : bisect_right(vals, high)])\n```\n\n<iframe src="https://leetcode.com/playground/2RVvrN38/shared" frameBorder="0" width="800" height="260"></iframe>\n\n**\u2705 YOU MADE IT TILL THE BONUS SECTION... YOUR GREAT EFFORT DESERVES UPVOTING THIS POST!**\n\n**Python.** DFS one-liner.\n```\nclass Solution:\n    def rangeSumBST(self, r, l, h):\n        \n        return 0 if not r else (l <= r.val <= h) * r.val + \\\n                               self.rangeSumBST(r.right, l, h) + \\\n                               self.rangeSumBST(r.left,  l, h)\n```
[]