# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(n)
    where, n is the number of nodes in given tree.
    NOTE: You misunderstood the definition of a balanced tree as least possible height for a binary tree for given nodes, when it's actually,
    for all nodes, the difference between depth of it's left subtree and right subtree is less than or equal to 1 level.
    Eg: [1,2,3,4,5,6,null,8]
    Took 8 min once, the definition was clarified, ask clarifying questions, don't assume!
    '''
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node):
            if not node:
                return 0
            left = check(node.left)
            right = check(node.right)
            if min(left, right) == -1 or abs(right-left) > 1:
                return -1
            return 1 + max(left, right)
        return False if check(root) == -1 else True

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(n)
    where, n is the number of nodes
    Solved in 9 mins, all by yourself! Good job! Solved before!
    NOTE: You used exception handling to break out of recursion early when you find an unbalanced subtree, 
    which logically is a neat trick to avoid unnecessary calculations, 
    however this approach is not very efficient in terms of performance in real world, 
    also considered un-pythonic approach, simply returning values is much more efficient and pythonic,
    refer your previous solution.
    '''
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            if not node:
                return 0
            left = height(node.left)
            right = height(node.right)
            if not -2 < left - right < 2:
                raise Exception("Not a balanced tree!")
            return 1 + max(left, right)
        
        try:
            height(root)
        except:
            return False
        return True