110_balanced_binary_tree.md

110. Balanced Binary Tree

Recursive solution

• Runtime: O(N)
• Space: O(H)
• N = Number of elements in list
• H = Height of tree

Since the definition of a balance tree is that for each node the difference between each children's height is never greater than 1. We can perform a post order traversal and then compare the heights given by both children. If we encounter an imbalance, we ignore anymore traversals and head back up to the root node using an arbitrary value like -1 to symbolize an imbalance.

Worst case is if the tree is balanced and we have to visit every node. However, no matter what, we will end up using at most O(H) space to traverse the tree.

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        
        def balance_helper(root):
            if root is None:
                return 0
            left = balance_helper(root.left)
            if left == -1:
                return -1
            right = balance_helper(root.right)
            if right == -1:
                return -1
            return max(left, right)+1 if abs(left-right) <= 1 else -1
        
        return balance_helper(root) != -1