Check if a tree is balanced or not

The problem, simply

You get a binary tree. The height of a tree is how many nodes you pass on the longest trip from its top down to a leaf. An empty tree has height 0.

The tree is balanced if, at every single node, the height of the left side and the height of the right side differ by at most 1. Answer true or false.

A story to remember it

Picture it

Examples

Way 1: the simple way

At every node, measure the height of the left side and the right side from scratch, and check the gap. Then do the same for both children.

1. If the node is empty, it is balanced.
2. Measure height(left) and height(right). If they differ by more than 1, answer false.
3. Otherwise check the left child and the right child the same way.

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int gap = Math.abs(height(root.left) - height(root.right));
        return gap <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

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

How long it takes: every node measures everything below it again. In a tree shaped like a long stick that adds up to about n * n / 2 steps, O(n^2). For a balanced tree it is closer to O(n log n). Extra room: the waiting helpers, O(h).

Way 2: the clever way

Measure each height only once, from the bottom up, and check the gap at the same moment. A helper returns the height of its subtree, or -1 if something below is broken.

1. An empty spot returns 0.
2. Ask the left child. If it says -1, return -1 right away.
3. Ask the right child. If it says -1, return -1 right away.
4. If the two heights differ by more than 1, return -1.
5. Otherwise return 1 + max(left, right).

class Solution {
    public boolean isBalanced(TreeNode root) {
        return check(root) != -1;
    }

    // height of this subtree, or -1 if it is not balanced
    private int check(TreeNode n) {
        if (n == null) return 0;
        int left = check(n.left);
        if (left == -1) return -1;            // broken below: pass it up
        int right = check(n.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;
        return 1 + Math.max(left, right);
    }
}

How long it takes: each node is visited once, O(n), and we stop early when we find a broken spot. Extra room: the waiting helpers, O(h), where h is the height. In a stick shaped tree that is O(n).

Watch out for

• Counting edges in one place and nodes in another. Pick one meaning of height and use it everywhere. The gap is the same either way.
• Using -1 as the signal is safe here because a real height is never negative.
• A very tall stick shaped tree can overflow the call stack in Java. Mention an iterative post order walk if the interviewer asks.

What interviewers ask next

• Return the height and the answer together without -1? Return a small pair {balanced, height}. It reads clearer but does the same work.
• What is the tallest a balanced tree with n nodes can be? About 1.44 log2(n). That is why balanced trees (AVL trees) keep search fast.
• Make a sorted array into a balanced search tree? Pick the middle as the root and repeat on both halves.
• Same idea, other problems: diameter of a tree and maximum path sum also return a height while tracking a second answer.

Remember this

Grown-up words: the seesaw check is a height balanced test; asking children first is post order traversal; the "broken" shout is a sentinel value; the waiting helpers are the call stack.