How do you determine if a binary tree is height-balanced?
Direct Answer
This question tests recursive thinking and tree traversal algorithms. It specifically focuses on calculating depths and comparing subtree heights.
Why Interviewers Ask This
Interviewers use this to gauge your proficiency with recursion and tree properties. A balanced tree is crucial for efficient operations like search and insert. They want to see if you can optimize the solution to avoid redundant calculations, moving beyond a naive O(n^2) approach to an optimal O(n) one.
How to Answer This Question
Define a balanced tree as one where the left and right subtrees of every node differ in height by no more than one. Start with a recursive helper function that returns the height of the subtree. If a subtree is unbalanced, return -1 immediately to propagate the failure up the stack. This avoids unnecessary traversals. Compare the heights of left and right children at each step to ensure the balance condition holds.
Key Points to Cover
- Recursive height calculation
- Early termination on imbalance
- Difference check at every node
- Optimized O(n) time complexity
Sample Answer
A binary tree is height-balanced if for every node, the depth of the two subtrees differs by at most one. I would implement a recursive function that calculates the height of the tree. If the left or right subtree return…
Common Mistakes to Avoid
- Calculating height separately for each node (O(n^2))
- Not handling null nodes correctly
- Returning boolean instead of height for propagation
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.