[Python] Simple dfs, explained
One way to solve this problem is just iterate over our tree and for each element check if it is range or not. However here we are given, that out tree is BST, t
One way to solve this problem is just iterate over our tree and for each element check if it is range or not. However here we are given, that out tree is `BST`, that is left subtree is always lesser than node lesser than right subtree. So, let us modify classical `dfs` a bit, where we traverse only nodes we need:\n\n1. Check value `node.val` and if it is in our range, add it to global sum.\n2. We need to visit left subtree only if `node.val > low`, that is if `node.val < low`, it means, that all nodes in left subtree less than `node.val`, that is less than `low` as well.\n3. Similarly, we visit right subtree only if `node.val < high`.\n\n**Complexity**: time complexity is `O(n)`, where `n` is nubmer of nodes in our tree, space complexity potentially `O(n)` as well. We can impove our estimations a bit and say, that time and space is `O(m)`, where `m` is number of nodes in our answer.\n\n```\nclass Solution:\n    def rangeSumBST(self, root, low, high):\n        def dfs(node):\n            if not node: return\n            if low <= node.val <= high: self.out += node.val\n            if node.val > low:  dfs(node.left)\n            if node.val < high: dfs(node.right)\n                \n        self.out = 0\n        dfs(root)\n        return self.out\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Depth-First Search']