Balanced Binary Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
A tree is height-balanced if, at every node, the heights of its two subtrees differ by at most 1. Check this.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Computing the height at every node separately repeats work. Can one pass do both jobs?
- Hint 2Return a special value (like -1) to mean "unbalanced somewhere below".
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A building inspector checks a tall tower with two wings at every floor. He does not climb from the top for every floor: he starts at the leaves and reports each wing's height upward. At each floor he compares the two wings; if they differ by more than one floor he shouts "unsafe!" and the whole inspection stops. Otherwise he reports 1 + the taller wing to the floor above.
- The obvious way
At each node compute both subtree heights from scratch: O(n²) in a skinny tree.
- The key insight
One recursive function returns the height of a subtree, or -1 if somewhere inside it the balance rule is broken. A node returns -1 if either child returned -1 or if the two child heights differ by more than 1; otherwise it returns 1 + the larger height. The tree is balanced if the root's answer is not -1.
- The algorithm
- Empty spot: height 0.
- Get the left height and the right height (stop with -1 if any is -1).
- They differ by more than 1? Return -1.
- Otherwise return 1 + the larger height. At the end the answer is: root's result is not -1.
Watch it run
Exampletree = [3, 9, 20, null, null, 15, 7]
Leaf 9 reports height 1.
9 -> 1
Where people slip
- Checking only the root's two heights is not enough: the rule must hold at EVERY node.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_balanced(root):
def height(node): # -1 means "unbalanced below"
if node is None:
return 0
left = height(node.left)
right = height(node.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return height(root) != -1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.