We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given a binary tree, determine whether it is height-balanced: for every node, the heights of its two subtrees differ by at most 1.
The tree is given as a level-order array with explicit nulls, where the children of index i sit at 2i + 1 and 2i + 2. An empty array is an empty tree.
An easy trees problem, graded against 6 test cases (3 of them hidden).
Recursive traversal of binary trees and BSTs - depth, validation, and path problems.
Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.
More Trees problems →The naive version asks "is the left balanced, is the right balanced, and do their heights differ by at most 1" - which calls a height function at every node, and that function walks the whole subtree. Heights get recomputed once per ancestor, so a skewed tree costs O(n^2).
The fix is to let one post-order traversal return both facts. Each call returns the subtree height, or a sentinel `-1` meaning "something below is unbalanced". A node that sees `-1` from either child propagates it straight up without inspecting anything else, so the whole tree is visited once.
The sentinel works because a real height is never negative, so there is no ambiguity between "unbalanced" and a legitimate value. Returning a tuple of (height, isBalanced) is equally correct and more explicit - worth mentioning in an interview as the readable alternative.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.