48.1 (Approach 1) | O(n)✅ | Python & C++(Step by step explanation)✅
Intuition\nThe problem involves determining whether a binary tree is balanced. A binary tree is balanced if the heights of its left and right subtrees differ by
# Intuition\nThe problem involves determining whether a binary tree is balanced. A binary tree is balanced if the heights of its left and right subtrees differ by at most 1 for every node in the tree.\n\n# Approach\nThe approach uses a Depth-First Search (DFS) traversal to check the balance of each subtree. The idea is to calculate the height of the left and right subtrees for each node and verify if the difference in heights is at most 1.\n\n1. The `isBalanced` function initializes a variable `h` to 0 and calls the DFS helper function.\n\n2. The `dfs` function performs the DFS traversal. It takes a node and a reference to the height variable (`h`) as input and returns a boolean indicating whether the subtree rooted at the current node is balanced. The function also updates the height of the subtree.\n\n3. Inside the `dfs` function:\n   - If the current node is null, set the height to -1 and return true (an empty subtree is considered balanced).\n   - Recursively calculate the height of the left and right subtrees.\n   - If either subtree is unbalanced or the difference in heights is greater than 1, return false.\n   - Update the height of the current subtree as 1 plus the maximum of the left and right subtree heights.\n   - Return true, indicating that the current subtree is balanced.\n\n4. The `h` variable is used to keep track of the height of each subtree.\n\n# Example\nConsider the following binary tree:\n```\n    3\n   / \\\n  9  20\n    /  \\\n   15   7\n```\nLet\'s go through the steps of the DFS approach:\n\n1. **Node 3:**\n   - Calculate the height of the left subtree (rooted at 9): 0\n   - Calculate the height of the right subtree (rooted at 20):\n     - Calculate the height of the left subtree (rooted at 15): 0\n     - Calculate the height of the right subtree (rooted at 7): 0\n     - Update the height of the right subtree as 1 + max(0, 0) = 1\n   - The difference in heights (abs(0 - 1)) is less than or equal to 1, so the subtree rooted at Node 3 is balanced.\n\n2. **Node 9:**\n   - Both left and right subtrees are null, so the height of the subtree is -1.\n   - The subtree rooted at Node 9 is considered balanced.\n\n3. **Node 20:**\n   - The difference in heights (abs(0 - 1)) is less than or equal to 1, so the subtree rooted at Node 20 is balanced.\n\n4. **Node 15 and Node 7:**\n   - Both are leaf nodes, so their height is 0.\n   - Both subtrees are considered balanced.\n\nThe entire tree is balanced because each subtree rooted at every node satisfies the condition of having a height difference of at most 1.\n\nTherefore, the binary tree is balanced.\n\n# Complexity\n- Time complexity: O(n), where n is the number of nodes in the binary tree. The algorithm visits each node once during the DFS traversal.\n- Space complexity: O(h), where h is the height of the binary tree. This represents the maximum depth of the recursive call stack. In the worst case, the space complexity is O(n) for a skewed tree, and in the best case, it is O(log n) for a balanced tree.\n\n# Code(Python)\n```python\nclass Solution:\n    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n         \n        def dfs(root):\n            # Base case: If the current node is None, return [True, 0]\n            if root == None:\n                return [True, 0]\n\n            # Recursive calls for left and right subtrees\n            left, right = dfs(root.left), dfs(root.right)\n            \n            # Check if the current subtree is balanced and update height\n            balanced = (left[0] and right[0] and abs(left[1] - right[1]) <= 1)\n            \n            # Return [balanced, height]\n            return [balanced, 1 + max(left[1], right[1])]\n\n        # Call the dfs function and return the result\n        return dfs(root)[0]\n```\n\n# Code(C++)\n```c++\nclass Solution {\npublic:\n    bool isBalanced(TreeNode* root) {\n        int h = 0 ;\n        return dfs(root , h);\n    }\nprivate:\n    bool dfs(TreeNode* root , int &h){\n        // Base case: If the current node is NULL, set height to -1 and return true\n        if(root == NULL){\n            h = -1;\n            return true;\n        }\n\n        // Variables to store heights of left and right subtrees\n        int left = 0;\n        int right = 0;\n\n        // Recursive calls for left and right subtrees\n        if (!dfs(root->left, left) || !dfs(root->right, right)) {\n            return false;\n        }\n        \n        // Check if the current subtree is balanced based on height difference\n        if (abs(left - right) > 1) {\n            return false;\n        }\n        \n        // Update height of the current subtree\n        h = 1 + max(left, right);\n        \n        // Return true, indicating the current subtree is balanced\n        return true;\n    }   \n};\n```\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
['Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Python3']