Balanced Binary Tree

EASY✓ CHIP-TIMEDLC #110 — FULL STATEMENT ↗

The drill: Check whether a binary tree stays height-balanced everywhere — at every single node, its two subtrees' heights may differ by at most one.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to decide whether it stays height-balanced everywhere inside it, not just at the top.

A tree counts as balanced only when, at every single node, the heights of its left and right subtrees differ by at most one. A single unbalanced node anywhere — even deep inside a huge tree — is enough to fail the whole check.

An empty tree, having no nodes to violate the rule, is considered balanced by definition.

EX 01

root = []

→ true

AN EMPTY TREE IS TRIVIALLY BALANCED

EX 02

root = [1]

→ true

SINGLE NODE

EX 03

root = [4, 2, 6, 1, 3, 5, 7]

→ true

PERFECTLY FULL TREE

the tree can hold anywhere from zero to a few thousand nodes
node values can be negative, zero, or positive
balance must hold at every node, subtree height difference capped at one
an empty tree counts as balanced

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

'Everywhere' means the check has to run at every node, not just the root. What's the naive way to check one node's balance?

HINT 2 THE STRUCTURE

At a node, compute both subtree heights and compare — but computing height from scratch at every node re-walks the tree over and over.

HINT 3 ONE STEP FROM THE ANSWER

Fold the check into the height computation itself: return the height as usual, but the instant one side comes back unbalanced, short-circuit with a sentinel and stop doing any more work.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SENTINEL POISONPATTERN · HEIGHT WITH A SENTINELroot = [1, 2, null, 3, null, 4]

STEP 1

Balanced means every node's two subtrees differ in height by at most one — this tree is a straight left-only spine down to depth 4. Check bottom-up, short-circuiting the instant an imbalance appears.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/balanced-binary-tree.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def check(node):
            if not node:
                return 0
            lh = check(node.left)
            if lh == -1:
                return -1
            rh = check(node.right)
            if rh == -1:
                return -1
            if abs(lh - rh) > 1:
                return -1
            return 1 + max(lh, rh)

        return check(root) != -1

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 16 LN

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        if not root:
            return True
        lh, rh = height(root.left), height(root.right)
        if abs(lh - rh) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

TIME O(N²)SPACE O(H)PYTHON · TRAINING PACE · 13 LN

class Solution {
    public boolean isBalanced(TreeNode root) {
        return check(root) != -1;
    }

    private int check(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int lh = check(node.left);
        if (lh == -1) {
            return -1;
        }
        int rh = check(node.right);
        if (rh == -1) {
            return -1;
        }
        if (Math.abs(lh - rh) > 1) {
            return -1;
        }
        return 1 + Math.max(lh, rh);
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 23 LN

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int lh = height(root.left);
        int rh = height(root.right);
        if (Math.abs(lh - rh) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

TIME O(N²)SPACE O(H)JAVA · TRAINING PACE · 20 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED