✅ 🔥 0 ms Runtime Beats 100% User🔥||  Code Idea ✅ ||  Algorithm & Solving Step  ✅ ||
\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n\n### Intuition: \nA height-balanced binary tree is defined as a binary tree where t
![Screenshot 2024-12-03 at 6.31.04\u202FPM.png](https://assets.leetcode.com/users/images/486358f5-d074-4349-ac74-cb02f224223b_1733230962.6953225.png)\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n\n### **Intuition:** \nA **height-balanced binary tree** is defined as a binary tree where the difference in height between the left and right subtrees of any node is at most 1. The height of a tree is the number of edges on the longest path from the root to any leaf node.\n\nTo determine if a binary tree is height-balanced, we need to check two conditions for every node:\n1. The left subtree and right subtree must be balanced.\n2. The height difference between the left and right subtrees should not exceed 1.\n\nIf both conditions hold true for all nodes, then the tree is height-balanced.\n\n### **Approach:**\n- **Height Calculation**: For each node, compute the height of its left and right subtrees. If the difference between the two heights is greater than 1, then the tree is not balanced.\n- **Recursive Strategy**: We can use recursion to calculate the height of each subtree while simultaneously checking if the tree is balanced. This avoids redundant calculations.\n\n### **Algorithm Steps:**\n1. **Base Case**: If the current node is `null`, return a height of `0`.\n2. **Left and Right Subtree Check**: Recursively check the left and right subtrees. For each node:\n   - If either the left or right subtree is unbalanced, return an "unbalanced" state (for example, `-1`).\n   - Otherwise, compute the height of the current node by taking the maximum height of its left and right subtrees and adding 1.\n3. **Height Difference**: At each node, if the absolute difference between the left and right subtree heights is greater than 1, return `-1` to indicate an unbalanced tree.\n4. **Final Check**: If the tree is balanced, return `true`; otherwise, return `false`.\n\n### **Time and Space Complexity:**\n- **Time Complexity**: O(n), where n is the number of nodes in the binary tree. We visit each node exactly once to calculate its height.\n- **Space Complexity**: O(h), where h is the height of the tree, due to recursion stack. In the worst case, the space complexity can be O(n), if the tree is skewed.\n\n---\n\n### **Code Implementations** : (Comments are added for easy to understand  )\n\n#### **C++ Solution** :\n\n```cpp\nclass Solution {\npublic:\n    bool isBalanced(TreeNode* root) {\n        return height(root) != -1;\n    }\n\nprivate:\n    int height(TreeNode* node) {\n        if (node == nullptr) return 0;  // Base case: empty tree has height 0\n        \n        // Recursively get the height of the left subtree\n        int leftHeight = height(node->left);\n        if (leftHeight == -1) return -1;  // If the left subtree is unbalanced, return -1\n        \n        // Recursively get the height of the right subtree\n        int rightHeight = height(node->right);\n        if (rightHeight == -1) return -1;  // If the right subtree is unbalanced, return -1\n        \n        // If the height difference between left and right subtrees is more than 1, return -1\n        if (abs(leftHeight - rightHeight) > 1) return -1;\n        \n        // Return the height of the current node\n        return max(leftHeight, rightHeight) + 1;\n    }\n};\n```\n\n---\n\n#### **Java Solution** :\n\n```java\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n        return height(root) != -1;\n    }\n\n    private int height(TreeNode node) {\n        if (node == null) return 0;  // Base case: empty tree has height 0\n\n        // Recursively get the height of the left subtree\n        int leftHeight = height(node.left);\n        if (leftHeight == -1) return -1;  // If the left subtree is unbalanced, return -1\n\n        // Recursively get the height of the right subtree\n        int rightHeight = height(node.right);\n        if (rightHeight == -1) return -1;  // If the right subtree is unbalanced, return -1\n\n        // If the height difference between left and right subtrees is more than 1, return -1\n        if (Math.abs(leftHeight - rightHeight) > 1) return -1;\n\n        // Return the height of the current node\n        return Math.max(leftHeight, rightHeight) + 1;\n    }\n}\n```\n\n---\n\n#### **Python Solution** :\n\n```python\nclass Solution:\n    def isBalanced(self, root: TreeNode) -> bool:\n        return self.height(root) != -1\n\n    def height(self, node: TreeNode) -> int:\n        if not node:\n            return 0  # Base case: empty tree has height 0\n\n        # Recursively get the height of the left subtree\n        leftHeight = self.height(node.left)\n        if leftHeight == -1:\n            return -1  # If the left subtree is unbalanced, return -1\n\n        # Recursively get the height of the right subtree\n        rightHeight = self.height(node.right)\n        if rightHeight == -1:\n            return -1  # If the right subtree is unbalanced, return -1\n\n        # If the height difference between left and right subtrees is more than 1, return -1\n        if abs(leftHeight - rightHeight) > 1:\n            return -1\n\n        # Return the height of the current node\n        return max(leftHeight, rightHeight) + 1\n```\n\n---\n\n### **Example Walkthrough** :\n\n#### Example 1:\n- **Input**:\n    - `root = [3, 9, 20, null, null, 15, 7]`\n- **Process**: \n    - The tree is balanced because for every node, the left and right subtrees have a height difference of no more than 1.\n- **Output**: `true`\n\n#### Example 2:\n- **Input**:\n    - `root = [1, 2, 2, 3, 3, null, null, 4, 4]`\n- **Process**: \n    - At node `2`, the left and right subtrees have a height difference of 2, so the tree is unbalanced.\n- **Output**: `false`\n\n#### Example 3:\n- **Input**:\n    - `root = []`\n- **Process**: \n    - An empty tree is trivially balanced.\n- **Output**: `true`\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/b8bfe3c3-00ac-4eba-87c4-a9985b27ea13_1733231116.7435446.png)\n
['Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3']