Check if all leaf nodes are at same level or not

The problem, simply

You get a binary tree. A leaf is a node with no children. The level of a node is how many steps it is below the root (the root is level 0).

Answer true if all the leaves are on the same level, and false if at least two leaves are on different levels.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write down the level of every leaf in a list. At the end, check that every number in the list is the same.

1. Walk the tree and carry the level.
2. At a leaf, add its level to the list.
3. Compare every entry with the first one.

import java.util.*;

class Solution {
    public boolean leavesSameLevel(TreeNode root) {
        List<Integer> levels = new ArrayList<>();
        collect(root, 0, levels);
        for (int lv : levels) if (lv != levels.get(0)) return false;
        return true;
    }

    private void collect(TreeNode n, int level, List<Integer> levels) {
        if (n == null) return;
        if (n.left == null && n.right == null) { levels.add(level); return; }
        collect(n.left, level + 1, levels);
        collect(n.right, level + 1, levels);
    }
}

How long it takes: one visit per node, O(n). Extra room: the list holds one number per leaf, and a tree can have about n / 2 leaves, so O(n).

Way 2: the clever way

We do not need the whole list. Keep only the level of the first leaf (the tape on the wall). Compare every later leaf with it, and stop as soon as one does not match.

1. Start with "no leaf seen yet" (level -1).
2. Walk the tree and carry the level.
3. At the first leaf, save its level.
4. At every other leaf, compare. On a mismatch, stop and answer false.

class Solution {
    private int firstLeafLevel;
    private boolean ok;

    public boolean leavesSameLevel(TreeNode root) {
        firstLeafLevel = -1;          // no leaf seen yet
        ok = true;
        walk(root, 0);
        return ok;
    }

    private void walk(TreeNode n, int level) {
        if (n == null || !ok) return;             // stop early after a mismatch
        if (n.left == null && n.right == null) {
            if (firstLeafLevel == -1) firstLeafLevel = level;   // put the tape here
            else if (level != firstLeafLevel) ok = false;
            return;
        }
        walk(n.left, level + 1);
        walk(n.right, level + 1);
    }
}

How long it takes: at most one visit per node, O(n), often less because we stop early. Extra room: only the waiting helpers, O(h).

Watch out for

• Forgetting to reset the saved level between test cases when you use fields.
• An empty tree. With no leaves, the usual answer is true. Say which answer you return.
• Going on after a mismatch. It is not wrong, but the early stop is a free speed win.

What interviewers ask next

• Can you do it row by row? Yes. Read the tree level by level with a queue. Once a row contains a leaf, every node in that row must be a leaf, and there must be no next row.
• Return the level of the shallowest leaf instead? That is the minimum depth of a tree. Row by row reading finds it fastest, because it stops at the first leaf.
• Is a tree with all leaves on one level always perfect? No. A node can still have just one child, as in the first example where 5 has only a left child.

Remember this

Grown-up words: the shelf height is the level or depth, the walk is a depth first search, and the tape mark is a single saved value instead of a list.