You are given root, the root of a binary tree (or nothing, for an empty tree).
The tree is balanced if, at every node, the heights of the left and right subtrees differ by
at most 1. A subtree's height is the number of nodes on its longest downward path, and an empty
subtree has height 0. Return true if the tree is balanced and false otherwise. An empty tree
is balanced.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [7, 3, 9, null, null, 8, 12]
- Output
- true
Example 2
- Input
- root = [5, 4, 6, 3, null, null, null, 2]
- Output
- false
Constraints
- The tree holds 0 to 1000 nodes.
- Every value is between −10⁴ and 10⁴.
Show the pattern
Trees
Whether a node is balanced depends on its subtrees' heights, and its own height comes from theirs too. One post-order pass can return both, so no height is worked out twice.
See trees in a visualiserShow the approach
Use one post-order recursion that returns a subtree's height, or −1 if some node inside it is
unbalanced. At a node, get both children's results. If either is −1, or they differ by more than
1, return −1. Otherwise return 1 + max(left, right). The tree is balanced exactly when the
root's result isn't −1.
Checking only the root isn't enough: a tree can be balanced at the root and lopsided further down. Each node is visited once.
Time: O(n) · Space: O(h) for the recursion, h the tree's height