✅100% Accepted || Worst to Best approaches with explanation || Easy to understand.
Read the below approaches.\n\nPlease upvote if you like it!! \n\nApproach 1: Naive approach (Not Optimised)\n\nIntuition + Approach:\n\n For a Balanced Binary T
**Read the below approaches.**\n\n***Please upvote if you like it!!*** \n\n**Approach 1:** Naive approach (Not Optimised)\n\n**Intuition + Approach:**\n\n* For a Balanced Binary Tree, Check left subtree height and right subtree height for every node present in the tree. Hence, traverse the tree recursively and calculate the height of left and right subtree from every node, and whenever the condition of Balanced tree violates, simply return false.\n* Condition for Balanced Binary Tree\n* **For all Nodes , Absolute( Left Subtree Height \u2013 Right Subtree Height ) <= 1**\n\n**Dry run :**\n\n![image](https://assets.leetcode.com/users/images/92d9778c-8347-4ce9-888a-6753a54fc8b3_1664313008.0877197.png)\n\n**~Time Complexity: O(N*N)** \n* **Reason:** ( For every node, Height Function is called which takes O(N) Time. Hence for every node it becomes N*N ) \n\n**~Space Complexity: O(1) ( Extra Space ) + O(H)**\n* **Reason:** ( Recursive Stack Space where \u201CH\u201D is the height of tree )\n```\n\n```\n\n**Approach 2:** Post Order Traversal ( Most optimised )\n\n**Intuition:** Can we optimize the above brute force solution? Which operation do you think can be skipped to optimize the time complexity?\n\n* Ain\u2019t we traversing the subtrees again and again in the above example?\n* Yes, so can we skip the repeated traversals?\n* What if we can make use of post-order traversal?\n* So, the idea is to use post-order traversal. Since, in postorder traversal, we first traverse the left and right subtrees and then visit the parent node, similarly instead of calculating the height of the left subtree and right subtree every time at the root node, use post-order traversal, and keep calculating the heights of the left and right subtrees and perform the validation.\n\n**Approach :**\n\n* Start traversing the tree recursively and do work in Post Order.\n* For each call, caculate the height of the root node, and return it to previous calls.  \n* Simultaneously, in the Post Order of every node , Check for condition of balance as information of left and right subtree height is available.\n* If it is balanced , simply return height of current node and if not then return -1.\n* Whenever the subtree result is -1 , simply keep on returning -1.\n\n**~Time Complexity: O(N)**\n**~Space Complexity: O(1) Extra Space + O(H) Recursion Stack space (Where \u201CH\u201D  is the height of binary tree)**\n\n**Dry run:-**\n\n![image](https://assets.leetcode.com/users/images/9e7c39a6-1756-40fa-9166-b75ec40cd46f_1664313277.571836.png)\n\n**Paper dry run:-**\n\n![image](https://assets.leetcode.com/users/images/cf43e954-8707-4355-923f-667a0fb15c33_1664313955.4142773.jpeg)\n\n**C++ Code:**\n\n```\nclass Solution {\npublic:\n    int solve(TreeNode* root){\n        if(!root) return 0;\n        int leftHeight=solve(root->left);\n        if(leftHeight == -1) return -1;\n        \n        int rightHeight=solve(root->right);\n        if(rightHeight==-1) return -1;\n        \n        if(!(abs(leftHeight-rightHeight)<=1)) return -1;\n        return max(leftHeight,rightHeight)+1;\n    }\n    bool isBalanced(TreeNode* root) {\n        return solve(root) !=-1;\n    }\n};\n```\n\n
['Depth-First Search', 'Recursion', 'C', 'Binary Tree', 'C++']