Given a binary tree, determine if it is height-balanced.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Example 3:
Input: root = [] Output: true
Constraints:
[0, 5000].-104 <= Node.val <= 104The goal of #110 Balanced Binary Tree is to determine whether the height difference between the left and right subtrees of every node is at most one. A straightforward idea is to compute the height of each subtree and verify the balance condition at every node. However, repeatedly calculating subtree heights can lead to unnecessary work.
A more efficient strategy uses Depth-First Search (DFS) with a post-order traversal. Starting from the leaves, compute the height of each subtree and propagate the result upward. If at any node the difference between the left and right subtree heights exceeds one, the tree is not balanced. Many implementations return a special value (for example -1) to signal imbalance and stop further computation early.
This approach ensures each node is visited only once while checking both subtree heights and balance conditions simultaneously. The method is efficient and commonly expected in technical interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Naive height check for each node | O(n^2) | O(h) |
| Optimized DFS with post-order traversal | O(n) | O(h) |
take U forward
This approach involves recursively calculating the height of each subtree and checking if the subtrees are balanced by ensuring the difference in height is not more than one.
Time Complexity: O(N^2), where N is the number of nodes in the tree, as we recalculate the height of subtrees multiple times. Space Complexity: O(N) due to recursion stack.
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12int height(TreeNode* node) {
13 if (!node) return 0;
14 return max(height(node->left), height(node->right)) + 1;
15}
16
17bool isBalanced(TreeNode* root) {
18 if (!root) return true;
19 int leftHeight = height(root->left);
20 int rightHeight = height(root->right);
21 if (abs(leftHeight - rightHeight) > 1) return false;
22 return isBalanced(root->left) && isBalanced(root->right);
23}This C++ solution follows a similar approach to the C implementation. We define a helper method, height, which evaluates the height of the binary tree recursively. At each step, we ensure that every subtree is balanced by checking the height difference criterion.
This optimized approach calculates the height and balance status of a tree in a single recursive function, thus avoiding recalculations by returning both height and balanced status in form of tuples or objects.
Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth.
1class
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations frequently appear in FAANG and other top tech company interviews. It tests understanding of tree traversal, recursion, and how to optimize repeated computations.
The optimal approach uses a depth-first search with post-order traversal. By computing subtree heights while checking the balance condition in the same traversal, each node is processed once, giving O(n) time complexity.
Post-order traversal processes the left and right subtrees before the current node. This makes it ideal for computing subtree heights first and then checking whether the current node satisfies the height-balanced condition.
A binary tree structure combined with recursion or an explicit stack is typically used. DFS traversal works best because it allows you to calculate subtree heights and verify the balance condition during the same pass.
In Java, an inner class Result is used to store both height and balanced status in the recursive process, ensuring early termination on detecting imbalance, thus optimizing computation.