169. Balanced Binary Tree

Why this mechanism works

A parent needs either an exact child height or evidence that the child is already unbalanced. Use -1 as a failure sentinel because real node-count heights are nonnegative. This combines validation and height computation into one traversal and can stop propagation immediately after a failure.

State and boundaries

height_or_fail(node) returns the exact nonnegative height if its entire subtree is balanced, otherwise -1.

Protocol

1. Return zero for None.
2. Summarize left and stop on failure.
3. Summarize right and stop on failure.
4. Reject a height difference greater than one.
5. Otherwise return one plus the larger height.

Visualization

child summaries: height 3 and height 1
abs(3-1)>1 -> return -1
every ancestor propagates failure, never recomputes height

Python implementation

from structures import build_tree

def is_balanced(root):
    def height_or_fail(node):
        if node is None:
            return 0
        left = height_or_fail(node.left)
        if left == -1:
            return -1
        right = height_or_fail(node.right)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return height_or_fail(root) != -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 is_balanced: def height_or_fail(node):
root=N1(val=1,left=N2,right=N3)

L5 height_or_fail: if node is None:
node=N1(val=1,left=N2,right=N3)

L5 height_or_fail: if node is None:
node=N2(val=2,left=N4,right=N5)

L5 height_or_fail: if node is None:
node=N4(val=4,left=None,right=None)

L5 height_or_fail: if node is None:
node=None

L7 height_or_fail: left = height_or_fail(node.left)
node=N4(val=4,left=None,right=None); left=0

L5 height_or_fail: if node is None:
node=None

L10 height_or_fail: right = height_or_fail(node.right)
node=N4(val=4,left=None,right=None); left=0; right=0

... 10 intermediate state changes omitted ...

L7 height_or_fail: left = height_or_fail(node.left)
node=N3(val=3,left=None,right=None); left=0

L5 height_or_fail: if node is None:
node=None

L10 height_or_fail: right = height_or_fail(node.right)
node=N3(val=3,left=None,right=None); left=0; right=0

L10 height_or_fail: right = height_or_fail(node.right)
node=N1(val=1,left=N2,right=N3); left=2; right=1

L4 is_balanced: def height_or_fail(node):
root=N1(val=1,left=N2,right=None)

L5 height_or_fail: if node is None:
node=N1(val=1,left=N2,right=None)

L5 height_or_fail: if node is None:
node=N2(val=2,left=N3,right=None)

L5 height_or_fail: if node is None:
node=N3(val=3,left=None,right=None)

L5 height_or_fail: if node is None:
node=None

L7 height_or_fail: left = height_or_fail(node.left)
node=N3(val=3,left=None,right=None); left=0

L5 height_or_fail: if node is None:
node=None

L10 height_or_fail: right = height_or_fail(node.right)
node=N3(val=3,left=None,right=None); left=0; right=0

... 2 intermediate state changes omitted ...

L10 height_or_fail: right = height_or_fail(node.right)
node=N2(val=2,left=N3,right=None); left=1; right=0

L7 height_or_fail: left = height_or_fail(node.left)
node=N1(val=1,left=N2,right=None); left=2

L5 height_or_fail: if node is None:
node=None

L10 height_or_fail: right = height_or_fail(node.right)
node=N1(val=1,left=N2,right=None); left=2; right=0

Why the solution is correct

The empty subtree satisfies the contract. If either child fails, the parent subtree contains an unbalanced node. Otherwise both child heights are exact; the local difference test is the only remaining condition. Returning the combined height preserves the contract for the parent.

Time and space

O(n) worst-case time and O(h) recursive stack space; short-circuit failures may visit fewer nodes.

Common mistakes

Checking only the root misses an unbalanced descendant. Treating -1 as an ordinary height can accidentally turn failure into a plausible parent result.

Reasoning card

Transfer exercise

Replace the sentinel with a tuple (balanced,height). Compare readability and the information available after failure.