Python 3   ||   6 lines,  two versions, w/ explanation   ||   T/S: 93% / 94%
A binary search tree is more than just a binary tree. For each node node, every node value in node\'s left tree is less than node.val, and every node value in n
A binary *search* tree is more than just a binary tree. For each node `node`, every node value in `node`\'s left tree is less than `node.val`, and every node value in `node`\'s right tree is greater than `node.val`.\n\nHere\'s the plan:\n- Traverse the tree recursively or iteratively, and at each node visited, return the sum of all qualifying node values in its two subtrees. However, for any `node`:\n\n- If `node.val` is less than `low`, then we know that each value in node\'s left subtree is also less than `low`; if so, we do not need to traverse *node*\'s left subtree.\n- Likewise, If `node.val` is greater than `high`, then we know that each value in `node`\'s right subtree is also greater than `high`; if so, we do not need to traverse `node`\'s right subtree.\n\nHere is a recursive version:\n\n```\nclass Solution: \n    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n\n        def dfs(node):\n\n            if not node: return 0\n\n            if node.val <  low: return dfs(node.right)\n            if node.val > high: return dfs(node.left )\n            \n            return dfs(node.left ) + dfs(node.right) + node.val\n\n        return dfs(root)\n```\n\n```\n```\n\nAnd here\'s a iterative version:\n\n```\nclass Solution: \n    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n\n        ans, stack = 0, deque([root])\n\n        while stack:\n            node = stack.pop()\n            if not node: continue\n\n            if   node.val <  low: stack.append(node.right)\n            elif node.val > high: stack.append(node.left )\n            else:\n                ans+= node.val\n                stack.append(node.left )\n                stack.append(node.right)\n                \n        return ans\n```\nhttps://leetcode.com/problems/range-sum-of-bst/submissions/1273539127/\n\nI could be wrong, but I think that, for each solution, time complexity is *O*(*N*) and space complexityis *O*(*H*), in which *N* ~ the number of nodes and *H* ~ the height of the tree.
['Python3']