Balanced tree✅ |  O( n )✅  | Python(Step by step explanation)✅
Intuition\nThe problem is to determine if a binary tree is balanced, which means that the difference in heights between the left and right subtrees of any node 
# Intuition\nThe problem is to determine if a binary tree is balanced, which means that the difference in heights between the left and right subtrees of any node is at most 1. The intuition is to perform a depth-first search (DFS) on the tree while simultaneously checking the balance condition for each node.\n\n# Approach\nThe approach is to implement a DFS function that returns two values for each node: whether the subtree rooted at the current node is balanced and the height of the subtree. This can be achieved using a recursive DFS traversal of the binary tree.\n\n1. Implement a recursive DFS function, `dfs(root)`, that takes a node as a parameter.\n2. Inside the DFS function, check if the current node is `None`. If it is, return `[True, 0]` to indicate an empty subtree, which is considered balanced.\n3. Recursively call the `dfs` function on the left and right children of the current node, and store the results in `left` and `right`, respectively.\n4. Calculate whether the current subtree is balanced by checking if both `left[0]` and `right[0]` are `True`, and if the absolute difference between `left[1]` (the height of the left subtree) and `right[1]` (the height of the right subtree) is at most 1.\n5. Return `[balanced, 1 + max(left[1], right[1])]` as the result for the current node, where `balanced` is `True` if the current subtree is balanced, and `1 + max(left[1], right[1])` represents the height of the current subtree.\n6. In the main function, `isBalanced(root)`, return `dfs(root)[0]` to check if the entire binary tree is balanced.\n\n# Complexity\n- Time complexity: O(n)\n  - The algorithm performs a depth-first traversal of the binary tree, visiting each node once.\n- Space complexity: O(h), where h is the height of the binary tree\n  - The space complexity is determined by the maximum height of the call stack during the recursive DFS traversal.\n  - In the worst case, when the tree is skewed (completely unbalanced), the space complexity is O(n).\n  - In the best case, when the tree is perfectly balanced, the space complexity is O(log(n)).\n\n```python\nclass Solution:\n    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n        def dfs(root):\n            if root is None:\n                return [True, 0]\n\n            left, right = dfs(root.left), dfs(root.right)\n            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1\n\n            return [balanced, 1 + max(left[1], right[1])]\n\n        return dfs(root)[0]\n```\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n\n\n
['Tree', 'Depth-First Search', 'Python3']