Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Balance must hold at every node, not just at the root. A node can be checked as soon as both child heights are known, so postorder traversal lets one recursive pass compute heights and detect any imbalance.

Approach

Initialize a shared result flag to true. Define the height of an empty subtree as zero.
Recursively obtain a node's left and right subtree heights. If their difference exceeds one, set the result flag to false. Never reset a failed flag while visiting another node.
Return one plus the larger child height to the parent. The displayed implementations continue computing heights even after discovering an imbalance.
After processing the root, return the flag. An empty tree remains balanced because its height calculation never encounters a violating node.

# 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:
        self.res = True

        def dfs(node):
            if not node: return 0
            l = dfs(node.left)
            r = dfs(node.right)
            if abs(l - r) > 1: self.res = False
            return max(l, r) + 1
        
        dfs(root)
        return self.res

Complexity analysis

For N tree nodes and height H, postorder DFS visits each node once: O(N) time and O(H) auxiliary space for recursion. Both displayed implementations are recursive, so an allowed highly skewed tree (up to 5000 nodes) can exceed the language runtime stack.