Balanced Binary Tree

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

Balanced Binary Tree. Given the root of a binary tree, return true if it's height balanced: at every node, the left and right subtrees differ in height by at most one.

Three, nine, twenty, with fifteen and seven under twenty: every node is within one, so true. In the second tree, the root's left side is three tall, its right just one: false. An empty tree is balanced: true.

The direct way: at every node, measure both subtrees from scratch. But each measurement walks everything below, so a deep node gets walked again for every ancestor. On a tall tree, that's n squared.

The key idea: measure once, from the bottom up. Each call returns its height, or minus one the moment anything below is unbalanced. That minus one bubbles straight up, and the rest of the tree is skipped. It's Maximum Depth's height recursion, plus one check.

In code, an empty node has height zero. If the left height is minus one, pass it up. Same for the right, or if the two differ by more than one. Otherwise, return one plus the taller side.

Now three, nine, twenty. Nine is a leaf: height one. Fifteen and seven: height one each. Twenty compares one and one: height two. The root compares one and two: they differ by one, fine. Height three, not minus one: true.

Each node is visited once: linear time. The recursion goes as deep as the tree: order h stack space.

Return heights, flag minus one, stop early. That's Balanced Binary Tree.