A feature-flag service stores mutually exclusive variants as a binary tree: each experiment has a left cohort and a right cohort of nested follow-on flags. A publish gate refuses a tree that is not height-balanced, so a flag evaluation cannot become a scan of every cohort. The intern version, at every node, called the existing maxDepth helper on the left child and again on the right. A dozen flags painted green. A million-node import from an acquired product still re-walked the same leaves from every ancestor.

Height-balanced means |lh - rh| <= 1 at every node, not only at the root. The binary tree post owns shape and traversals. Maximum Depth already owns 1 + max(left, right). Calling it twice at every node recomputes those heights from every ancestor. Here we only care about returning the height, or -1 the moment a node fails the gap.

The problem

Given the root of a binary tree, return whether it is height-balanced: at every node, the heights of the left and right subtrees differ by at most one. An empty tree is balanced. A single node is balanced.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees. The second root’s two sides have equal height; a child does not.

      3
     / \
    9  20
      /  \
     15   7        →  true

        1
       / \
      2   2
     /     \
    3       3
   /         \
  4           4    →  false

[]                 →  true
[1]                →  true

Note: Comparing depths only at the root is necessary and not sufficient. The left 2 above has heights 2 and 0.

Max-depth at every node is the honest brute force

At each node, compute maxDepth of the left subtree and of the right, reject if they differ by more than one, then recurse into both children so a hidden grandchild cannot sneak through. Correct. Extra: every ancestor re-walks the same descendants.

boolean isBalancedNaive(TreeNode root) {
    if (root == null) {
        return true;
    }
    int lh = maxDepth(root.left);
    int rh = maxDepth(root.right);
    if (Math.abs(lh - rh) > 1) {
        return false;
    }
    return isBalancedNaive(root.left) && isBalancedNaive(root.right);
}

int maxDepth(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

At a dozen nodes this is a rounding error. On a million-node spine, node i rescans the remaining n - i nodes. Worst case is O(n²). The intended answer never starts a second height walk: a node returns its height, or -1 if it or a descendant already failed.

Return height, or -1, from one post-order walk

Ask the left child first. If it returns -1, propagate -1 — that subtree is already illegal, and you can skip the right walk. If both heights are real and |lh - rh| > 1, this node fails: return -1. Otherwise return 1 + max(lh, rh), the same recurrence Maximum Depth uses.

heightOrFail(9) = 1     heightOrFail(15) = heightOrFail(7) = 1
heightOrFail(20) = 1 + max(1, 1) = 2
heightOrFail(3)  = |1 - 2| <= 1, return 3     →  true

heightOrFail(4) = 1
heightOrFail(3) = 1 + max(1, 0) = 2
heightOrFail(left 2): |2 - 0| > 1             →  -1
heightOrFail(1): left already -1              →  false

The Java is that recurrence. isBalanced is whether the root’s walk returned a height instead of -1.

boolean isBalanced(TreeNode root) {
    return heightOrFail(root) != -1;
}

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

Time is O(n) — each node is visited once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack is the same bound without blowing the JVM stack.

Empty: null returns 0, not -1. One node: both children 0, |0 - 0| <= 1, return 1. No extra branch. Do not return -1 for null — null is height 0, and an empty tree is balanced.

What interviewers usually poke next

  • Only the root. Draw the second sample. Equal heights at 1 are not a proof.
  • Diameter of Binary Tree. Longest path between any two nodes, counted in edges. Later sibling — /interview/trees/easy/diameter-of-binary-tree/ — it also returns height as a side product. Do not compute diameters in isBalanced.
  • A pair instead of -1. Some boards return (height, ok) so a sentinel cannot collide with a real height. This prompt’s live nodes are height at least 1, so -1 is unambiguous — and null must stay 0, not -1.
  • Million-node spine. Recursion depth is O(h). Say you would switch to an explicit stack so the JVM does not blow the stack.

You are done with this problem when you can reject a tree whose root looks even, and you can say empty and a single node are balanced without a special case.