How do you determine if a binary tree is height-balanced?
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 returns a negative value indicating imbalance, the function propagates this result up. At each node, I calculate the height of both children. If the absolute difference is greater than one, I return -1. Otherwise, I return the maximum height plus one. This single-pass approach ensures O(n) time complexity.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you add two numbers represented by linked lists?
Medium
AmazonWrite Selenium and Java code to automate an Amazon search
Medium
InfosysHow do you implement binary search on a sorted array?
Easy
MicrosoftWhat is the difference between value type and reference type?
Easy
TCSConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDiscuss ACID vs. BASE properties
Easy
Microsoft