Balanced Binary Tree
Asked at Anduril
Problem
Balanced Binary Tree asks whether a binary tree is height-balanced: for every node, the heights of its left and right subtrees differ by at most one. The interesting part is doing it in a single pass instead of recomputing heights over and over.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Easy | View all Anduril questions → |
How to Think About It
Naive approach: for each node, compute height(left) and height(right) and compare, then recurse into both children. Heights get recomputed for every ancestor, which is O(n²) on a skewed tree.
Key insight: compute height bottom-up (post-order), and have the same function report imbalance. Return the height if the subtree is balanced, or a sentinel like -1 if it is not.
At each node: get lh = h(left) and rh = h(right). If either is -1, or abs(lh - rh) > 1, return -1. Otherwise return 1 + max(lh, rh).
Once any subtree reports -1, every ancestor immediately passes it upward — this early exit is what makes the algorithm O(n).
Edge cases: an empty tree is balanced (height 0). A single node is balanced. A "vine" of three nodes going left is not.
Optimal Approach
Step 1: Define h(node):
If node is null, return 0.
lh = h(node.left); if lh == -1, return -1.
rh = h(node.right); if rh == -1, return -1.
If abs(lh - rh) > 1, return -1.
Return 1 + max(lh, rh).
Step 2: The tree is balanced iff h(root) != -1.
Each node is visited exactly once.
Time: O(n). Space: O(h) recursion stack, where h is the tree height.
What Trips People Up in Real Interviews
Only checking the root. The definition applies to every node — a tree whose root is balanced can still have an unbalanced subtree deep inside.
Writing the top-down O(n²) version and stopping there. Always mention that height and balance can be computed together in one post-order pass.
Confusing "balanced" with "complete" or "perfect". Balanced only restricts the height difference to at most one at each node.
Returning a tuple and forgetting to short-circuit. It is correct, but the -1 sentinel version is shorter and makes the early exit obvious.
Solution Code
def isBalanced(root):
def h(node):
if not node:
return 0
lh = h(node.left)
if lh == -1:
return -1
rh = h(node.right)
if rh == -1:
return -1
if abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
return h(root) != -1Frequently Asked Questions
What is the Balanced Binary Tree problem?
Balanced Binary Tree asks whether a binary tree is height-balanced: for every node, the heights of its left and right subtrees differ by at most one. The interesting part is doing it in a single pass instead of recomputing heights over and over.
How do you solve Balanced Binary Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Balanced Binary Tree?
Balanced Binary Tree is asked at Anduril. It is a easy difficulty problem.
What are common mistakes on Balanced Binary Tree?
- Only checking the root. The definition applies to every node — a tree whose root is balanced can still have an unbalanced subtree deep inside.
- Writing the top-down `O(n²)` version and stopping there. Always mention that height and balance can be computed together in one post-order pass.
- Confusing "balanced" with "complete" or "perfect". Balanced only restricts the height difference to at most one at each node.
- Returning a tuple and forgetting to short-circuit. It is correct, but the `-1` sentinel version is shorter and makes the early exit obvious.