O(n) Time complexity | bottom-up DFS | Short and simple explained
Intuition\nGiven the definition of a balanced tree, we know that a tree is not balanced when the difference between heights of the left and right subtree is ove
# Intuition\nGiven the definition of a balanced tree, we know that a tree is **not balanced** when the difference between heights of the left and right subtree is over 1:\n `abs(height_left - height_right) > 1` *(abs: absolute value)*\nThe basic approach is:\n* Traverse the tree\n* Calculate the height of the left and right subtree\n* If it\'s not balanced (by using the formular above), then return false.\n* Return true when all nodes are passed\n\nBut for the best performance, we want to return false right after we have found the unbalanced subtree. So we add another step before calculating the height of subtrees: if the left or right subtree is unbalanced, then return false.\n\nWe don\'t want to repeat the traversal of the subtree to check balance and then calculate height. So we just do all once for each node.\n\nThe height at a node is obtained by it\'s children height + 1: `max(height(i.left), height(i.right)) + 1`\n\n# Approach\nTraverse each node recursively and return the height of it, if the subtree at that node is not balanced, then return -1:\n1. If the node is `null`, return 0\n2. Get the height of left subtree, if it\'s -1, then return -1\n3. Get the height of right subtree, if it\'s -1, then return -1\n4. If the difference between the heights of left and right subtree > 1 then return -1\n5. Finally, return false if the final height is -1, else return true\n# Complexity\n- Time complexity: $$O(n)$$\nFor each node, we compare the heights of it\'s children and get it\'s height in constance time.\n\n- Space complexity: $$O(n)$$ \nThe recursive stack may contain all nodes if the tree is skewed (each node only has left child)\n# Code\n```Python3 []\nclass Solution:\n    def isBalanced(self, root: Optional[TreeNode]) -> bool:\n        def height(root):\n            if root == None:\n                return 0\n            \n            h_left = height(root.left)\n            if h_left < 0:\n                return -1\n            h_right = height(root.right)\n            if h_right < 0 or abs(h_left - h_right) > 1:\n                return -1\n\n            return max(h_left, h_right) + 1\n        \n        return height(root) >= 0\n```\n```C++ []\n#include <algorithm>\nclass Solution {\npublic:\n    int height(TreeNode* root) {\n        if (!root) {\n            return 0;\n        }\n        int hLeft = height(root->left);\n        if (hLeft < 0) {\n            return -1;\n        }\n        int hRight = height(root->right);\n        if (hRight < 0 || std::abs(hLeft - hRight) > 1) {\n            return -1;\n        }\n        return std::max(hLeft, hRight) + 1;\n    }\n\n    bool isBalanced(TreeNode* root) {\n        return height(root) >= 0;\n    }\n};\n```\n```Java []\nclass Solution {\n    int height(TreeNode root) {\n        if (root == null) {\n            return 0;\n        }\n        int hLeft = height(root.left);\n        if (hLeft < 0) {\n            return -1;\n        }\n        int hRight = height(root.right);\n        if (hRight < 0 || Math.abs(hLeft - hRight) > 1) {\n            return -1;\n        }\n        return Math.max(hLeft, hRight) + 1;\n    }\n\n    public boolean isBalanced(TreeNode root) {\n         return height(root) >= 0;\n    }\n}\n```\n```Kotlin []\nclass Solution {\n    fun height(root: TreeNode?): Int {\n        if (root == null) {\n            return 0\n        }\n        val hLeft = height(root.left);\n        if (hLeft < 0) {\n            return -1\n        }\n        val hRight = height(root.right);\n        if (hRight < 0 || abs(hLeft - hRight) > 1) {\n            return -1\n        }\n        return max(hLeft, hRight) + 1\n    }\n\n\n    fun isBalanced(root: TreeNode?): Boolean {\n        return height(root) >= 0\n    }\n}\n```
['Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3', 'Kotlin']