Is the Tree Height-Balanced at Every Node
Solve this ProblemYou are given the root of a binary tree. Decide whether it is height-balanced: at every node, the height of the left subtree and the height of the right subtree differ by at most 1. (The height of a subtree is the number of nodes on its longest downward path; an empty subtree has height 0.) An empty tree is balanced.
Checking the two heights at every node with a separate height function repeats a lot of work. A single bottom-up pass can report a subtree's height and its balance status together.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 (the values never affect the answer) - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
The height of a subtree is the number of nodes on its longest downward path (0 for an empty subtree). A tree is height-balanced if at EVERY node the heights of the left and right subtrees differ by at most 1. Return true or false; an empty tree is balanced
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recompute the Heights at Every Node
BruteFollow the definition literally. At a node, measure the height of the left and right subtrees with a separate height function; if they differ by more than 1 the tree is not balanced. Otherwise the node is fine, and the same check has to hold for the left subtree and for the right subtree. The flaw: the height function walks an entire subtree every time it is called, and it is called again at every node below — so nodes near the bottom are re-measured over and over. On a tall thin tree this adds up to O(n²).
O(n²)O(h)1class Solution {
2 public boolean isHeightBalanced(TreeNode root) {
3 if (root == null) return true;
4 if (Math.abs(height(root.left) - height(root.right)) > 1) return false;
5 return isHeightBalanced(root.left) && isHeightBalanced(root.right);
6 }
7
8 private int height(TreeNode node) {
9 if (node == null) return 0;
10 return 1 + Math.max(height(node.left), height(node.right));
11 }
12}Optimal — One Bottom-Up Pass That Reports Height or "Unbalanced"
OptimalFold the height calculation and the balance check into one recursive function. For a node, first get the left subtree's answer, then the right subtree's answer. Each answer is either a real height (0 or more) or the special value -1 meaning "somewhere below here the balance rule is already broken". A -1 from either side is passed straight up (and we stop immediately — the other subtree may not even be visited). Otherwise compare the two heights: if they differ by more than 1, return -1; if not, return 1 + the taller height. The tree is balanced exactly when the root's answer is not -1. Every node is visited once: O(n) time and O(h) space.
O(n)O(h)1class Solution {
2 public boolean isHeightBalanced(TreeNode root) {
3 return check(root) != -1;
4 }
5
6 private int check(TreeNode node) {
7 if (node == null) return 0;
8 int left = check(node.left);
9 if (left == -1) return -1;
10 int right = check(node.right);
11 if (right == -1) return -1;
12 if (Math.abs(left - right) > 1) return -1;
13 return 1 + Math.max(left, right);
14 }
15}