☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Check for balanced binary tree

Medium TUF ID 127 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, decide whether it is height-balanced: for every node, the heights of its left and right subtrees differ by at most 1. The height of an empty tree is 0 and of a single node is 1. An empty tree is balanced.

Constraints: 0 ≤ n ≤ 5000 nodes in the LeetCode version, values fit in an int.

Example 1

tree (level order) = [3, 9, 20, null, null, 15, 7]

     3
    / \
   9   20
      /  \
     15   7

answer = true       // at 3: heights 1 and 2; at 20: 1 and 1; leaves: 0 and 0

Example 2

tree (level order) = [1, 2, 2, 3, 3, null, null, 4, 4]

         1
        / \
       2   2
      / \
     3   3
    / \
   4   4

answer = false      // at the root: left height 3, right height 1

The word “every” matters. Look at [1, 2, 2, 3, null, null, 3, 4, null, null, 4]: the root’s left and right subtrees both have height 3, so the root alone looks perfect, but each 2 has a chain of length two on one side and nothing on the other. The tree is not balanced. Checking only the root is the classic wrong answer.

Approach 1: Brute force

Intuition. Translate the definition literally. For the current node, compute the height of the left subtree and of the right subtree with a separate height function, and fail if they differ by more than one. Then apply the same check to both children. The problem is that the height function walks an entire subtree, and we call it again for every node inside that subtree, so the same nodes are measured over and over.

Algorithm.

  1. If the node is null, return true.
  2. If |height(left) - height(right)| > 1, return false.
  3. Return check(left) && check(right).
static int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

static boolean bruteForce(TreeNode root) {
    if (root == null) return true;
    if (Math.abs(height(root.left) - height(root.right)) > 1) return false;
    return bruteForce(root.left) && bruteForce(root.right);
}

Complexity. Time O(n^2) as a worst-case bound: each of the n nodes can trigger height computations over a subtree of size up to n. On a balanced tree the cost is O(n log n), because a node’s height is recomputed once for every ancestor and a balanced tree has only O(log n) levels. Space O(h) for the recursion.

Approach 2: Optimal, one post-order pass

Intuition. The waste in Approach 1 is that heights are computed top-down, again and again. Flip the direction: compute heights bottom-up, once, and check the balance condition at each node while its two child heights are already in hand. A post-order traversal does exactly that, because a node is processed after both its children.

We still need a way to report “this subtree is already unbalanced” upward. Heights are never negative, so a return value of -1 can serve as a sentinel: it means “unbalanced somewhere below”. Once any call returns -1, every caller above it returns -1 immediately without doing more work, and the root’s result tells us the answer. One function returns both pieces of information, height and validity, in a single int.

Algorithm.

  1. checkHeight(null) = 0.
  2. Compute lh = checkHeight(left); if it is -1, return -1.
  3. Compute rh = checkHeight(right); if it is -1, return -1.
  4. If |lh - rh| > 1, return -1.
  5. Otherwise return 1 + max(lh, rh), the real height.
  6. The tree is balanced exactly when checkHeight(root) != -1.
static boolean optimal(TreeNode root) {
    return checkHeight(root) != -1;
}

static int checkHeight(TreeNode node) {
    if (node == null) return 0;
    int lh = checkHeight(node.left);
    if (lh == -1) return -1;
    int rh = checkHeight(node.right);
    if (rh == -1) return -1;
    if (Math.abs(lh - rh) > 1) return -1;
    return 1 + Math.max(lh, rh);
}

Dry run on Example 2:

node lh rh returns
4 (left) 0 0 1
4 (right) 0 0 1
3 (with children) 1 1 2
3 (leaf) 0 0 1
2 (left of root) 2 1 3
2 (right of root) 0 0 1
1 (root) 3 1 -1, difference is 2

The root returns -1, so the answer is false.

Complexity. Time O(n): every node is visited at most once, and each visit does constant work. Space O(h) for the recursion, where h is the height, O(log n) for balanced trees and O(n) for a chain (although a chain longer than two nodes is detected as unbalanced as soon as the recursion returns from its bottom).

Why the early exits matter. They are needed for correctness, not only for speed. Without them a -1 from one side would be mixed with a real height from the other. Take lh = -1 (the left subtree is broken) and rh = 0 (no right child): the difference is exactly 1, so the node would pass the balance test and return 1 + max(-1, 0) = 1, a perfectly ordinary height, and the failure would vanish. Two failing children, lh = rh = -1, would return 0 and vanish the same way. Returning -1 the moment a child reports it keeps the sentinel intact all the way to the root, and as a bonus skips the right subtree once the left one has failed.

Edge cases and pitfalls