Balanced Binary Tree
Easy · Trees · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, determine whether it is height-balanced.
A binary tree is height-balanced when, for every node, the heights of its left and right subtrees differ by at most one. An empty tree is balanced.
Examples
Input: root = [6,2,9,1,4,null,11] Output: true
At every node the two subtree heights differ by at most one.
Input: root = [6,2,9,1,null,null,null,0] Output: false
Node 2 has a left subtree of height 2 and an empty right subtree.
Input: root = [] Output: true
An empty tree is balanced by definition.
Constraints
- The number of nodes is in the range [0, 5000]
- -10^4 <= Node.val <= 10^4
Approaches
- Check every node from the top — time O(n²) worst, O(n log n) when balanced, space O(h)
Follow-up
What if the tree changes over time, with nodes inserted and deleted, and must stay balanced? That is what self-balancing search trees do: an AVL tree stores each node's height, rechecks the balance on the path back up after every change, and fixes any node that tips over with a rotation.
Related problems
Start free on Cariara · Coding problems · System design studio
