110. Balanced Binary Tree

Quick Identifier

Topic: trees
Pattern: Tree DFS (post-order)
Difficulty: Easy
Companies: Amazon, Google, Bloomberg, Meta, Apple
Frequency: High
LeetCode: 110

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(h) from the optimal approach.
Core Mechanism: Given the root of a binary tree, determine if it is height-balanced: for every node, the absolute difference between the heights of its left and right subtrees is at most 1.

Concept Explanation

Given the root of a binary tree, determine if it is height-balanced: for every node, the absolute difference between the heights of its left and right subtrees is at most 1.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

"Balanced" binary tree definition (AVL-style height gap)
Check every subtree, not only the root’s children
Often solved by returning sentinel height -1 when imbalanced

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(n²) time — for each node, compute subtree heights with separate DFS each time.
Better — O(n) time — cache heights in a map (two passes).
Optimal — O(n) time / O(h) stack — single post-order DFS: return -1 if child imbalanced or |left−right| > 1; else return 1 + max(left, right).

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isBalanced(root *TreeNode) bool {
	var height func(*TreeNode) int
	height = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		leftHeight := height(node.Left)
		if leftHeight == -1 {
			return -1
		}
		rightHeight := height(node.Right)
		if rightHeight == -1 {
			return -1
		}
		diff := leftHeight - rightHeight
		if diff < 0 {
			diff = -diff
		}
		if diff > 1 {
			return -1
		}
		if leftHeight > rightHeight {
			return 1 + leftHeight
		}
		return 1 + rightHeight
	}
	return height(root) != -1
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function isBalanced(root) {
	function height(node) {
		if (node === null) {
			return 0;
		}
		const leftHeight = height(node.left);
		if (leftHeight === -1) {
			return -1;
		}
		const rightHeight = height(node.right);
		if (rightHeight === -1) {
			return -1;
		}
		if (Math.abs(leftHeight - rightHeight) > 1) {
			return -1;
		}
		return 1 + Math.max(leftHeight, rightHeight);
	}
	return height(root) !== -1;
}