JuniorCodeVery commonNot answered yet
Check whether a binary tree is balanced
Given the root of a binary tree, return true if it is height-balanced: at every node the heights of the left and right subtrees differ by at most 1.
Requirements:
- O(n) time — do not recompute subtree heights at every node (that is O(n²)).
- Check every node, not just the root's children.
- An empty tree counts as balanced.
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
};
bool isBalanced(TreeNode* root) {
// your code here
}Write the implementation.
Heights of left and right subtrees differ by at most 1 at every node. The optimal O(n) DFS returns the subtree height, or −1 as a sentinel for 'unbalanced', so height computation and balance check happen in one pass.
- ✗Using the O(n²) approach with a separate height function called at every node
- ✗Only checking the root's children instead of every node recursively
- ✗Not returning a sentinel value — returning just bool loses the height information needed by the parent
- →What is an AVL tree and how does it maintain balance on insertions?
- →What is the difference between height-balanced and weight-balanced trees?
Contents
Task
Write a function to check whether a binary tree is height-balanced (left and right subtrees differ in height by at most 1 at every node).
Solution
// O(n) — returns -1 as "unbalanced" sentinel
int checkHeight(TreeNode* root) {
if (!root) return 0;
int l = checkHeight(root->left); if (l == -1) return -1;
int r = checkHeight(root->right); if (r == -1) return -1;
return (std::abs(l - r) > 1) ? -1 : 1 + std::max(l, r);
}
bool isBalanced(TreeNode* root) { return checkHeight(root) != -1; }Key points
- Naive approach calls
height()at every node: O(n²). - Sentinel (-1) approach combines height and balance check in one O(n) DFS.
- Stack depth is O(h): O(log n) balanced, O(n) worst case.
Contents
