Solution: Checking the Order

The tree has to pass two checks: the order property and the structure property. We write each check as its own method, and the answer is both of them together:

public static <T extends Comparable<T>> boolean isMinHeap(Node<T> root) {
  return isOrdered(root) && isComplete(root);
}

On this page, we write isOrdered. On the next page, we write isComplete.

Which pairs to compare

The order property is a statement about a node and its children. So we compare each node with its children, and nothing else.

That is less than what the validate-BST problem in the search tree chapter’s practice needed. There, a value had to be in order with every ancestor, not just its parent. A value could be larger than its parent and still be out of order, because it sat in the left subtree of a node it was larger than. So that check carried a lower and an upper bound down the tree.

A heap does not need bounds. If every parent is no larger than its children, then every node is no larger than everything below it. To see why, follow any path down from a node. Each step goes from a parent to a child, and each step can only keep the value the same or make it larger. So the value at the top of the path is the smallest on the path.

The method

isOrdered follows the same pattern as the recursive tree methods from the tree chapter. An empty tree has no pairs to check, so it is ordered. Otherwise, compare the node with each child it has, and then check both subtrees:

private static <T extends Comparable<T>> boolean isOrdered(Node<T> node) {
  if (node == null) {
    return true;
  }
  if (node.left != null && node.left.value.compareTo(node.value) < 0) {
    return false;  // the left child outranks its parent
  }
  if (node.right != null && node.right.value.compareTo(node.value) < 0) {
    return false;  // the right child outranks its parent
  }
  return isOrdered(node.left) && isOrdered(node.right);
}

The comparison is < 0, not <= 0, because a min-heap allows a child to equal its parent.

On Example 2, isOrdered returns false when it compares 0 with its parent 2. On Example 3, every comparison passes, so isOrdered returns true.

The cost

Each node is visited once, and each visit does at most two comparisons. So isOrdered is $O(n)$. The recursion goes as deep as the height of the tree.