Balanced Binary Tree
You get the root of a binary tree. A binary tree is height balanced if, for every node in the tree, the heights of its left and right subtrees differ by at most 1. The height of a subtree is the number of nodes on its longest path down, and an empty subtree has height 0.
Return true if the tree is height balanced, and false otherwise. An empty tree is balanced. The tree is written in level order, with null for a missing child.
Examples
Input root = [3, 9, 20, null, null, 15, 7]
Output true
Input root = [1, 2, 2, 3, 3, null, null, 4, 4]
Output false
At the root, the left height is 3 and the right height is 1.
Input root = []
Output true
Constraints
- 0 <= number of nodes <= 500
- -100 <= node value <= 100
Stuck? Take one hint at a time
Common mistakes
- Checking the balance only at the root, which misses a lopsided subtree deeper down.
- Comparing the number of nodes in the two subtrees instead of their heights.
- Returning the height without a signal for "unbalanced", so a violation below the root is lost.
- Using the height of the whole tree instead of the heights of the two subtrees at each node.
Questions an interviewer may ask next
- Build a balanced binary search tree from a sorted array. (Pick the middle element as the root.)
- Rebalance an unbalanced binary search tree. (Rotations, as in AVL trees.)
- Allow a difference of at most k between subtree heights. What changes?
- Return the lowest node at which the tree stops being balanced.
root
[3,9,20,null,null,15,7]
Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.