110. Balanced Binary Tree

At a Glance

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

Problem (one-liner)

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}