Balanced Binary Tree

Given the root of a binary tree, return true if it is height-balanced — for every node, the heights of its left and right subtrees differ by at most 1 — and false otherwise.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

A tree is balanced when every node's two subtree heights differ by at most 1.

Naively you'd compute height at every node — that's O(n^2).

Fold the balance check into a single bottom-up height computation for O(n).

Common doubts

It computes height (an O(n) walk) at every one of the n nodes, so the work multiplies to O(n^2) on skewed trees.

It computes each node's height exactly once during a postorder pass and checks the balance condition using the heights already in hand.

Yes — both trivially satisfy the height condition.

Interview follow-ups

· What an interviewer asks next.

Return a sentinel height of -1 to mean 'already unbalanced'; any parent seeing -1 propagates it up without more work.

AVL trees enforce exactly this per-node height condition; red-black trees use a looser black-height invariant.

Fun facts

This per-node height condition is precisely the AVL-tree invariant that guarantees O(log n) operations.
The -1 sentinel trick turns the balance check into an early-exit recursion that stops at the first violation.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]
Output: true
Every node's two subtree heights differ by at most 1.

Example 2

Input: root = [1, 2, 2, 3, 3, null, null, 4, 4]
Output: false
The left child's subtrees have heights 2 and 0 — a difference of 2.

Constraints

- The number of nodes is in the range [0, 5000] - -10^4 <= Node.val <= 10^4

A tree is height-balanced when every node's two subtrees differ in height by at most 1. The naive check recomputes height at each node (O(n²)); the optimal one computes height once, bottom-up, and flags an imbalance the moment it sees subtree heights differing by more than 1.

Prerequisites

Before you start

· Concepts used directly in the solution.

Tree height. 1 + max(left height, right height); an empty tree is 0.

Postorder recursion. Compute both subtree heights before judging the node — and reuse them.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Balanced at the root only, or everywhere?”

At every node — the height condition must hold throughout the tree.

“Is an empty tree balanced?”

Yes, trivially.

The ideal opening — say it like this

A tree is balanced if at every node the two subtree heights differ by at most one.

Rather than recompute height at each node, I compute height bottom-up once and set a flag the moment any node violates the condition.

Understand the problem

Worked example — tree [1, 2, 2, 3, null, null, 3, 4, null, null, 4]

        1
       / \
      2   2
     /     \
    3       3
   /         \
  4           4
node 2 (left): left height 2, right height 0 -> differ by 2 -> NOT balanced
answer: false

Key observations

1Aha

Balance must hold at every node

A single deep-vs-shallow node anywhere makes the whole tree unbalanced.

2Aha

Compute height once, check on the way up

The height recursion already visits every node; folding the balance check into it avoids the O(n²) recomputation.

3Aha

A sentinel can short-circuit

Returning a special height (e.g. −1) as soon as imbalance is found lets deeper calls bail out early.

Brute force vs optimal

	Top-down (recompute height)	Bottom-up (height + flag)
Idea	At each node, compute both heights and compare	Compute height once, flag imbalance on the way up
Time	O(n^2)	O(n)
Space	O(height)	O(height)

The bottom-up version reuses each height instead of recomputing it. Full code is in the Approaches selector below.

Summary

Key takeaway

Compute subtree heights bottom-up in a single postorder pass, and flag the tree unbalanced the instant any node's two heights differ by more than 1. O(n) time, O(height) space.

height(node):
    if node is null: return 0
    lh = height(node.left); rh = height(node.right)
    if |lh - rh| > 1: mark unbalanced
    return 1 + max(lh, rh)