← Back to DSA Animator
Balanced Binary Tree LC #110 Easy DFS · Sentinel -1
Problem

Given a binary tree, determine if it is height-balanced. A binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1
Input: root = [3,9,20,null,null,15,7]
Output: true
Explanation: Max height diff at any node is 1.
Example 2
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: Left subtree depth 4, right depth 2 — diff = 2 > 1.
Example 3
Input: root = [1,2,3,4,5]
Output: true
Constraints: 0 ≤ number of nodes ≤ 5000  |  −104 ≤ Node.val ≤ 104
Try Examples
Custom:
Approach
DFS Post-order with Sentinel −1
height() returns actual height if subtree is balanced, or −1 as a sentinel for "unbalanced". A single O(n) pass — once −1 is returned, it propagates up immediately.
Binary Tree
Processing
Balanced ✓
Unbalanced ✗
Returning
Visited
Balance Checker — Current Node
Waiting for first node…
Height Return Table
NodeL.HR.H|diff|return
No rows yet…
Variables
Node
—
L height
—
R height
—
return
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Recursion Stack
Stack is empty — not started
Algorithm Steps
1
Base case: node == null → return 0 (null height is 0)
2
Recurse left: L = height(node.left) — if L == −1, propagate −1 immediately
3
Recurse right: R = height(node.right) — if R == −1, propagate −1 immediately
4
Check: |L − R| > 1 → this node is unbalanced, return −1
5
Return 1 + max(L, R) — the actual height of this balanced subtree
Time
O(n)
Space
O(h)
Why it Works

Using −1 as sentinel avoids a second pass. As soon as any subtree is unbalanced, all ancestor calls propagate −1 upward instantly — O(n) single-pass check. The recursion visits every node exactly once in post-order (children before parent), so when we check |L−R|, both subtree heights are already available. If the root receives a real height (≥ 0), the tree is balanced.