[Python] simple dfs, explained
What we need to do here is just to traverse our tree, using for example dfs and check balance for every node.\n\ndfs(node) here returns depth of subtree with ro
What we need to do here is just to traverse our tree, using for example dfs and check balance for every node.\n\n`dfs(node)` here returns depth of subtree with root in `node`. If it is `None`, depths is equal to `0`. We evaluate depths of left and right subtee and return maximum of them plus one. Also we check balance and if absolute difference is more than `1`, we can mark variable `self.Bal` as False: we can state now that tree is not balanced.\n\n**Complexity**: time complexity is `O(n)`, space complexity is `O(h)` as any classical dfs have.\n\n```\nclass Solution:\n    def isBalanced(self, root):\n        self.Bal = True\n        \n        def dfs(node):\n            if not node: return 0\n            lft, rgh = dfs(node.left), dfs(node.right)\n            if abs(lft - rgh) > 1: self.Bal = False\n            return max(lft, rgh) + 1\n            \n        dfs(root)\n        return self.Bal\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Depth-First Search']