Balanced Binary Tree

Intuition

• Unfortunately, unless you do some crazy try-catch logic to handle the moment when there is a local node that is not height balanced, you need to simply pass False back up the tree the moment you find such a node.
• You need to check every node since, as shown in the notes, you only have a binary tree, and therefore, you could have a case where a local node is not height balanced, yet the root node is.

Runtime

$O(N)$ for going through every node in the tree, where N is the number of nodes in the tree.

Code

# 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:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def r(isBalanced, node):
            if not node:
                return [True, 0]
 
            left_is_balanced, left_height = r(True, node.left)
            right_is_balanced, right_height = r(True, node.right)
 
            if not (left_is_balanced and right_is_balanced):
                return [False, None]
 
            if abs(left_height - right_height) > 1:
                return [False, None]
            return [True, 1 + max(left_height, right_height)]
 
        return r(True, root)[0]

Notes

---

References

https://leetcode.com/problems/balanced-binary-tree/