Java Solution from pratik
An empty tree is height-balanced. \n\n- A non-empty binary tree T is balanced if: \n1. Left subtree of T is balanced \n2. Right subtree of T is balanced \n3. Th
- An empty tree is height-balanced. \n\n- A non-empty binary tree T is balanced if: \n1. Left subtree of T is balanced \n2. Right subtree of T is balanced \n3. The difference between heights of left subtree and right subtree is at most `1`\n\nThe diagram below shows two trees, one of them is height-balanced and other is not. The second tree is not height-balanced because height of left subtree is 2 more than height of right subtree.\n\n![image](https://assets.leetcode.com/users/images/a888bbf2-39bc-4ae9-87d1-242a1126fdfd_1632409301.648122.jpeg)\n\n\n- If recursive call after conditional check, then its top down.\n- If recursive calls before conditional check, then its bottom up. \n\n**Solutiion 1: Top Down Approach:**\n\n**Time Complexity:** O(N<sup>2</sup>)\n- For the current node root, calling `getHeight()` for its left and right children actually has to access all of its children, thus the complexity is `O(N)`. \n- This is being done for each node in the tree, so the overall complexity of `isBalanced()` will be `O(N * N)` = O(N<sup>2</sup>)\n\n**Space complexity:** `O(H)` - the maximum depth of function call stack\n\n```\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n        if (root == null) {\n            return true;\n        }\n\n        int leftHeight = getHeight(root.left);\n        int rightHeight = getHeight(root.right);\n\n        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);\n    }\n\n    private int getHeight(TreeNode root) {\n        if (root == null) {\n            return 0;\n        } else {\n            return 1 + Math.max(getHeight(root.left), getHeight(root.right));\n        }\n    }\n}\n```\n\n**Solution 2: Bottom Up Approach:**\n\n- In Top Down Approach, we perform redundant calculations when computing the `height`. In each call to `getHeight()`, we require that the heights of subtrees also be computed. Therefore, when working top down we will compute the height of a subtree once for every parent. \n- We can remove this redundancy by first recursing on the children of the current node and then using their computed height to determine whether the current node is balanced.\n\n**Algorithm:**\n1. The bottom-up approach is a reverse of the logic of the top-down approach, since we first check if the child subtrees are balanced before comparing their heights.\n1. Check if the child subtrees are balanced. If they are, use their heights to determine if the current subtree is balanced as well as to calculate the height of current subtree.\n\n**Time Complexity**: `O(N)`\n- For every subtree, we compute its height in constant time as well as compare the height of its children.\n- Instead of calling `getHeight()` explicitly for each child node, the height of the current node is returned in recursion. \n- When the sub tree of the current node (inclusive) is balanced, the function `getHeight()` returns a non-negative value as the height, otherwise `-1` is returned. \n- According to the `leftHeight` and `rightHeight` of the two children, the parent node could check if the subtrees are balanced in order to decide its return value.\n- In bottom up approach, each node in the tree will be accessed once. Thus the time complexity is `O(N)`\n\n**Space complexity:** `O(H)` - the maximum depth of function call stack\n\n```\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n        return getHeight(root) != -1;\n    }\n\n    private int getHeight(TreeNode root) {\n        if (root == null)\n            return 0;\n\n        int leftHeight = getHeight(root.left);\n        if (leftHeight == -1) {\n            return -1;\n        }\n\n        int rightHeight = getHeight(root.right);\n        if (rightHeight == -1) {\n            return -1;\n        }\n\n        if (Math.abs(leftHeight - rightHeight) > 1) {\n            return -1;\n        } else {\n            return 1 + Math.max(leftHeight, rightHeight);\n        }\n    }\n}\n```
[]