Check if a Binary Tree is Heap

The problem, simply

You get a binary tree made of real nodes with left and right links. Say if it is a max heap. Two things must both be true:

1. Shape: the tree is complete. Every row is full except maybe the last, and the last row is filled from the left with no gaps.
2. Order: every parent is greater than or equal to each of its children.

A story to remember it

Picture it

Examples

Way 1: the simple way

Read the tree row by row with a waiting line, a queue, exactly like level order traversal. In a complete tree, once you meet a missing child, every child after it must be missing too.

1. Put the root in the line. Set gap = false.
2. Take a node from the front. Look at its left child, then its right child.
3. If a child is missing, set gap = true.
4. If a child is there but gap is already true, the tree has a hole. Return false.
5. If a child is bigger than the node, the order is broken. Return false.
6. Otherwise put the child at the back of the line.

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public boolean isHeap(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> line = new ArrayDeque<>();
        line.add(root);
        boolean gap = false;
        while (!line.isEmpty()) {
            TreeNode node = line.poll();
            for (TreeNode child : new TreeNode[] { node.left, node.right }) {
                if (child == null) { gap = true; continue; }
                if (gap) return false;                 // a node after a hole
                if (child.val > node.val) return false; // child beats parent
                line.add(child);
            }
        }
        return true;
    }
}

How long it takes: every node joins and leaves the line once, O(n). Extra room: the line holds a whole row, up to about n / 2 nodes, O(n).

Way 2: the clever way

Use the cinema seats. A tree with n nodes is complete exactly when its nodes use seats 0 to n - 1, with seat numbers given the same way an array heap stores them.

1. Count the nodes, n.
2. Walk the tree with recursion, carrying the seat number. The root gets seat 0. The left child of seat i gets 2i + 1, the right child gets 2i + 2.
3. If any node gets a seat >= n, there is a hole. Return false.
4. If any child is bigger than its parent, return false.

class Solution {
    public boolean isHeap(TreeNode root) {
        int n = count(root);
        return check(root, 0, n);
    }

    private int count(TreeNode node) {
        if (node == null) return 0;
        return 1 + count(node.left) + count(node.right);
    }

    private boolean check(TreeNode node, int seat, int n) {
        if (node == null) return true;
        if (seat >= n) return false;                          // a hole before this node
        if (node.left != null && node.left.val > node.val) return false;
        if (node.right != null && node.right.val > node.val) return false;
        return check(node.left, 2 * seat + 1, n)
            && check(node.right, 2 * seat + 2, n);
    }
}

How long it takes: one walk to count and one walk to check, O(n). Extra room: the recursion goes as deep as the tree, O(h). For a real heap h is about log n. For a long thin tree the counting walk can go n deep, but the checking walk stops as soon as a seat number reaches n.

Watch out for

• A tree that leans left, like [3, 2, null, 1], has the right order but is not complete. Node 1 gets seat 3 while only seats 0 to 2 exist.
• Seat numbers grow like 2^depth. On a very deep thin tree they overflow int. In Way 2 the walk returns false long before that, as soon as a seat passes n. If you compute seats any other way, use long.
• For a min heap, flip the two comparisons.
• An empty tree: decide with the interviewer. Most judges say true.

What interviewers ask next

• Check a min heap instead? Flip > to < in the two child checks.
• Given an array instead of a tree? The shape is always complete, so only check a[i] >= a[2i + 1] and a[i] >= a[2i + 2] for every parent i < n / 2.
• Check only that the tree is complete (LeetCode 958)? Use either way without the value checks.
• Can you do it in one pass? Yes, with the queue way, or with a post-order walk that returns the height and whether each subtree is perfect or complete. Be careful: a check like "left count is between right count and twice it plus one" is not enough to prove completeness.

Remember this

Grown-up words: the seats are array indexes of a binary heap, no holes means a complete binary tree, parent beats child is the max heap property, the waiting line is a queue for breadth first search, and the walk with seat numbers is a depth first search.