✅ 35ms| 96.09% | Easy solution | DFS | Step-by-Step Explanation
Intuition\n\nThe first thought is to check if a binary tree is height-balanced, which means that the difference in height between the left and right subtrees of
# Intuition\n\nThe first thought is to check if a binary tree is height-balanced, which means that the difference in height between the left and right subtrees of every node should not exceed 1. The problem can be approached by traversing the tree and checking this height difference at each node while also calculating the height of the tree.\n\n# Approach\n\nThe approach uses `Depth-First Search (DFS)` to traverse the tree. The key idea is to write a recursive function `dfs` that:\n1. Checks whether the left and right subtrees are balanced.\n2. Computes the height of the left and right subtrees.\n3. Determines if the current node is balanced by comparing the heights of its left and right subtrees.\n4. Propagates this information upwards in the recursion.\n\nThe function returns a pair: the first value indicates whether the subtree is balanced, and the second value is the height of the subtree. The final answer is obtained by checking the balance status of the entire tree starting from the root.\n\n# Complexity\n- Time complexity:\nThe time complexity is $$O(n)$$, where $$n$$ is the number of nodes in the tree. This is because each node is visited exactly once to calculate its height and check its balance condition.\n\n- Space complexity:\nThe space complexity is $$O(h)$$, where $$h$$ is the height of the tree. This is the space required for the recursion stack. In the worst case, for a skewed tree, $$h$$ could be $$O(n)$$, but for a balanced tree, $$h$$ is $$O(\\log n)$$.\n\n---\n\n# Code\n```python3 []\n# Definition for a binary tree node.\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\nclass Solution:\n    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n        def dfs(node: Optional[TreeNode]) -> int:\n            if not node: return [True, 0]\n            l, r = dfs(node.left), dfs(node.right)\n            b = (l[0] and r[0] and abs(l[1] - r[1]) <= 1)\n            return [b, 1 + max(l[1], r[1])]\n        return dfs(root)[0]\n```\n\nYour updated solution is well-structured and more efficient. Let me break down how this code works:\n\n# Code Explanation\n\n#### The `dfs` Function:\n- **Base Case**: \n  - If the `node` is `None` (i.e., it\'s a leaf node or an empty tree), return `[True, 0]`. This indicates that an empty tree is balanced (`True`) and has a height of `0`.\n  \n- **Recursive Case**:\n  - The function performs a depth-first search (DFS) on both the left and right subtrees of the current `node`:\n    - `l = dfs(node.left)` computes whether the left subtree is balanced and its height.\n    - `r = dfs(node.right)` computes whether the right subtree is balanced and its height.\n  - It then checks if the current node is balanced:\n    - A node is balanced if both left and right subtrees are balanced (`l[0] and r[0]`) and the height difference between them is at most `1` (`abs(l[1] - r[1]) <= 1`).\n    - `b` stores the result of this balance check.\n  - The function returns a list where:\n    - The first element (`b`) indicates whether the subtree rooted at `node` is balanced.\n    - The second element (`1 + max(l[1], r[1])`) is the height of the subtree rooted at `node`.\n\n#### The `isBalanced` Function:\n- This function simply calls the `dfs` function starting from the `root` of the tree and returns whether the entire tree is balanced (`dfs(root)[0]`).\n\n### Example Walkthrough\n\nLet\u2019s go through an example to see how this works:\n\n#### Testcase: `[3,9,20,null,null,15,7]`\n\nTree structure:\n```\n    3\n   / \\\n  9   20\n     /  \\\n    15   7\n```\n\n1. **Node 9**:\n   - Both left and right are `None`, so `dfs(node.left)` and `dfs(node.right)` return `[True, 0]`.\n   - The node is balanced, so `dfs(9)` returns `[True, 1]`.\n\n2. **Node 15** and **Node 7**:\n   - Both are leaf nodes, so `dfs(15)` and `dfs(7)` return `[True, 1]`.\n\n3. **Node 20**:\n   - Left subtree (15) returns `[True, 1]`.\n   - Right subtree (7) returns `[True, 1]`.\n   - Both subtrees are balanced, and their heights are equal, so `dfs(20)` returns `[True, 2]`.\n\n4. **Node 3**:\n   - Left subtree (9) returns `[True, 1]`.\n   - Right subtree (20) returns `[True, 2]`.\n   - Both subtrees are balanced, and their height difference is `1`, so `dfs(3)` returns `[True, 3]`.\n\nSince the entire tree is balanced, the `isBalanced` function returns `True`.
['Depth-First Search', 'Binary Tree', 'Python3']