The machine must decide whether the tree is height-balanced: for every node, the heights of the left and right subtrees differ by at most one. This is a per-node property, not just a root-level one — a subtree buried deep in the left branch can be unbalanced while the root still looks fine.
The key insight is that a single post-order DFS can answer both questions at once. Each recursive call returns the height of its subtree, and when a call discovers its children differ by more than one, it signals invalid upward. Combining the two concerns keeps the machine at a single pass over the tree.
The approach has three steps. First, if the node is null, return height 0 — it is trivially balanced. Second, recurse on both children; if either returns the invalid sentinel, propagate it upward immediately without further work. Third, compare the two heights; if they differ by more than one, return the sentinel, otherwise return 1 plus the larger height. Time is O(n) because every node is visited once, and space is O(h) for the call stack.
The trickiest edge case is that a subtree can fail while the current node's own heights look fine — the machine must check the sentinel from each child before trusting any height arithmetic. Also note that a skewed chain of length 3 is unbalanced at its third node even though the subtree at the root has height difference exactly 1 on one side.
def isBalanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
right = check(node.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(root) != -1