BALANCED BINARY TREE
Intuition\n Describe your first thoughts on how to solve this problem. \n1. Base Case:\n   - If the current node is null, it\'s essentially an empty subtree, wh
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. **Base Case**:\n   - If the current node is null, it\'s essentially an empty subtree, which is inherently balanced. So, in this case, we return `true` to indicate that this subtree is balanced.\n\n2. **Calculate Heights**:\n   - The code calculates the height of the left subtree and the height of the right subtree. It does this by recursively calling the `height` method.\n   - The `height` method calculates the height of a binary tree from the current node downward.\n\n3. **Check Balance**:\n   - After obtaining the heights of the left and right subtrees, the code calculates the absolute difference between these heights.\n   - If the absolute difference is greater than 1, it means that the current subtree is unbalanced, as the difference in heights violates the balanced tree definition. In this case, we return `false`.\n\n4. **Recursion**:\n   - We then recursively apply the same procedure to check if both the left and right subtrees are balanced. We do this by calling the `isBalanced` method on them.\n   - The results of these recursive calls are stored in `isLeftBalanced` and `isRightBalanced`.\n\n5. **Final Decision**:\n   - Finally, we check if both the left and right subtrees are balanced (`isLeftBalanced` and `isRightBalanced` are both `true`). If they are, it implies that the current subtree is balanced as well, and we return `true`. Otherwise, we return `false`.\n\nIn essence, the code traverses the binary tree recursively, checking the balance condition at each node. If any subtree is found to be unbalanced, the function returns `false`, indicating that the entire tree is not balanced. Otherwise, if all subtrees are balanced, the function returns `true`, confirming that the binary tree is balanced.\n\nThe time complexity is O(n) because it visits each node in the tree once, and the space complexity depends on the height of the tree, ranging from O(log n) for balanced trees to O(n) for skewed trees.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHere\'s a step-by-step approach for the code you provided:\n\n1. **Base Case**: If the `root` of the current subtree is `null`, it is considered balanced because an empty subtree is always balanced. So, return `true`.\n\n2. **Calculate Heights**: Calculate the height of the left subtree and the height of the right subtree using the `height` method. The `height` method calculates the height of a binary tree recursively.\n\n3. **Check Balance**: Calculate the absolute difference between the heights of the left and right subtrees. If this difference is greater than 1, the current subtree is not balanced, so return `false`.\n\n4. **Recursion**: Recursively check if both the left and right subtrees are balanced by calling the `isBalanced` method on them. Store the results in `isLeftBalanced` and `isRightBalanced`.\n\n5. **Final Decision**: If both the left and right subtrees are balanced (`isLeftBalanced` and `isRightBalanced` are both `true`), then the current subtree is balanced, and you can return `true`. Otherwise, return `false`.\n\nHere\'s the code\'s logic summarized:\n\n- The base case checks if the current subtree is empty (null), and if so, returns true.\n- It calculates the heights of the left and right subtrees.\n- It checks if the absolute difference in heights is greater than 1, which indicates that the subtree is not balanced.\n- If both the left and right subtrees are balanced, it returns true, indicating that the current subtree is balanced.\n- This process is applied recursively to check the entire binary tree.\n\nThe code works correctly to determine whether a given binary tree is balanced or not.\n\n# Complexity\n1. Time Complexity:\n   - The code recursively traverses the entire binary tree.\n   - For each node in the tree, it calculates the height of its left and right subtrees by calling the `height` method.\n   - Therefore, the time complexity of this code is O(n), where \'n\' is the number of nodes in the binary tree. In the worst case, it visits every node once.\n\n2. Space Complexity:\n   - The space complexity is determined by the recursive call stack during the execution of the code.\n   - In the worst case, the code can have a maximum of \'h\' recursive calls on the call stack, where \'h\' is the height of the binary tree.\n   - Therefore, the space complexity of this code is O(h), where \'h\' is the height of the binary tree.\n   - In the worst case, if the binary tree is skewed (i.e., it degenerates into a linked list), the height \'h\' can be equal to \'n\', resulting in a space complexity of O(n).\n   - In a balanced binary tree, the height \'h\' is O(log n), resulting in a space complexity of O(log n).\n\nSo, the space complexity can range from O(log n) to O(n), depending on the shape of the binary tree. The time complexity is O(n) in all cases.\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n        if(root==null)\n        return true;\n        int l=height(root.left);\n        int r=height(root.right);\n        if(Math.abs(l-r)>1)\n        return false;\n        boolean isLeftBalanced=isBalanced(root.left);\n        boolean isRightBalanced=isBalanced(root.right);\n        return isLeftBalanced && isRightBalanced;\n    }\n     public static int height(TreeNode root){\n        if(root==null)\n        return 0;\n        int l=height(root.left);\n        int r=height(root.right);\n        return 1+Math.max(l,r);\n    }\n\n}\n```
['Tree', 'Recursion', 'Java']