PPractick

The problem

A search index keeps data in binary trees and rebalances them when they get lopsided, because deep, skewed trees make lookups slow. A tree is height-balanced when, at every node, the heights of the left and right subtrees differ by at most 1. Checking each node separately recomputes heights over and over (O(n²) on skewed trees). The standard fix computes height bottom-up and returns a sentinel −1 as soon as any subtree is unbalanced, so the check and the height come out of a single O(n) pass.

Example: [3, 9, 20, null, null, 15, 7] → true; [1, 2, 2, 3, 3, null, null, 4, 4] → false.

Function signature

bool isBalanced(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
[3, 9, 20, null, null, 15, 7]	true
[1, 2, 2, 3, 3, null, null, 4, 4]	false	The root's subtrees have heights 3 and 1
[1, 2, 3, 4]	true	Every difference is at most 1
[1, null, 2, null, 3]	false	A chain of three
[]	true

(Confirm: the condition applies at every node, not just the root; height counts nodes.)

How interviewers phrase it

• "Given a binary tree, determine if it is height-balanced" (LeetCode 110).

Clarifying questions to ask

1. Balanced at every node or only at the root? (Every node.)
2. Does an empty tree count as balanced? (Yes.)
3. Is O(n) expected? (Yes: the O(n²) version is the usual first attempt.)

Follow-ups to expect

1. "Why is the naive approach O(n²)?"
2. "How does the −1 sentinel help?"
3. "Why does imbalance at the root's check alone not suffice?"
4. "How do AVL trees use this?"
5. "Complexity?"

Related questions

• Maximum Depth in BT Medium
• Check if two trees are identical or not Medium
• Symmetric Binary Tree Medium
• Preorder Traversal Easy
• Inorder Traversal of Binary Tree Easy
• Postorder Traversal Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in