← DSA Atlas
Dedicated problem page · #110

Balanced Binary Tree

EasyTrees and Binary Search TreesPost-order height with early -1 signalBottom-up DFS returning height or sentinel
Solve on LeetCode ↗
110
EasyTrees and Binary Search TreesBottom-up DFS returning height or sentinelPost-order height with early -1 signal

Balanced Binary Tree

Given the root of a binary tree, determine whether it is height-balanced: for every node, the heights of its left and right subtrees differ by at most one.

Open official problem prompt ↗
In plain English

Check that no node in the tree has left and right subtrees whose heights differ by more than one.

Picture it like this

Like inspecting a mobile hung from the ceiling: at every joint the two arms must hang at nearly the same length, or the whole thing tilts. One badly lopsided joint condemns the mobile.

Example
Input
root = [3, 9, 20, null, null, 15, 7]
Output
true
Why
Every node's left and right subtree heights differ by at most 1, so the tree is balanced.
Constraints
The number of nodes is in the range [0, 5000]-10^4 <= Node.val <= 10^4
Pattern lesson

See the pattern, then code

Post-order height with early -1 signal
Recognition clue

You must check a height condition at EVERY node; computing height top-down repeatedly is wasteful, so the signal is to fuse the height computation with the balance check bottom-up.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Compute each subtree's height once in post-order and, the moment any subtree is unbalanced, propagate a sentinel -1 upward to short-circuit the rest of the work.

New words, made simpleKnow these before the algorithm
Height
The number of nodes (or edges) on the longest path from a node down to a leaf.
Height-balanced
At every node, |left height - right height| <= 1.
Sentinel value
A special return (-1) that signals imbalance and cuts recursion short.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Compute height at every node separately

Recomputes heights repeatedly; degenerates to quadratic on skewed trees.

For each node call a height function on its subtrees and compare.

Time O(n^2)Space O(h)
Best choicePost-order height with -1 sentinel

Single pass; balance and height are decided together.

Return the height, or -1 as soon as any subtree is unbalanced.

Time O(n)Space O(h)
The rule we keep true

Invariant

height(node) returns the true subtree height if that subtree is balanced, and -1 the moment any node within it violates the balance condition.

Why this is correct

Reasoning

By post-order, when a node is processed both child heights are final. If either child already reported -1, the imbalance is propagated. Otherwise the node checks its own |left-right| condition. Thus -1 appears at the root iff some node in the tree is unbalanced, and each node is visited exactly once giving O(n).

The algorithm in three movesSay these aloud before coding
1Recurse to get left height; if it is -1, bubble -1 up

height(9)=1, height(15)=1, height(7)=1

2Recurse to get right height; if it is -1, bubble -1 up

height(20)=2 (|1-1|<=1)

3If |left - right| > 1, return -1 to mark imbalance

at root: |1-2|<=1 -> height 3, balanced

4Otherwise return 1 + max(left, right) as this node's height

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
91
202
153
74
1 · Readeach leaf
2 · Askheight?
3 · Update statereturn 1
4 · Resultbalanced so far
Key takeaway

Heights computed bottom-up; root sees left=1, right=2, difference 1, so balanced.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-5Empty height

    A missing subtree has height 0.

  2. 2
    Lines 6-10Propagate imbalance early

    If a child subtree already reported -1, stop and bubble it up.

  3. 3
    Lines 11-12Balance check

    A difference greater than 1 marks this node's subtree unbalanced with -1.

  4. 4
    Lines 13Return height

    Balanced node returns 1 plus its taller child's height.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty tree -> true (height 0)
  • Single node -> true
  • Skewed chain of 3+ nodes -> false
  • Perfectly balanced tree -> true
!

Common beginner mistakes

  • Recomputing height independently of the balance check, causing O(n^2)
  • Comparing heights but forgetting to bubble the -1 sentinel, so imbalance deep in the tree is missed
  • Using height (edges vs nodes) inconsistently between recursion and comparison
Check your understanding

Why does returning -1 as a sentinel let the algorithm run in O(n) instead of O(n^2)?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split