Full lesson preview

Check if a tree is height-balanced

Determine whether a binary tree is height-balanced: for every node, the heights of left and right subtrees differ by at most 1.

Python practice28 minTrees & Binary TreesAdvancedLast updated March 29, 2026

Problem statement

A binary tree is height-balanced if for every node in the tree, the difference in height between the left and right subtrees is at most 1. Given the root of a binary tree, return True if the tree is height-balanced, otherwise return False. You should aim for O(n) time by computing subtree heights while checking balance in a single traversal.

Task

Implement an efficient algorithm to check whether a binary tree is height-balanced (O(n) time).

Examples

Balanced tree example

Input

TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))

Output

True

Left subtree height = 1, right subtree height = 2 at root, difference is 1; all nodes satisfy balance condition.

Input format

A single binary tree root (TreeNode or None).

Output format

A boolean value: True if the tree is height-balanced, otherwise False.

Constraints

Number of nodes in the tree is up to 10^5. Aim for O(n) time and O(h) recursion space where h is tree height.

Samples

Sample 1

Input

TreeNode(1, TreeNode(2, TreeNode(3)))

Output

False

This is a left-skewed tree; some nodes have subtree height difference > 1.