Problem: Validate a Heap

In the chapter, we decided by hand whether a tree is a heap. This problem asks for a method that makes the same decision.

Use the binary tree node from the tree chapter:

public class Node<T> {
  public T value;
  public Node<T> left;
  public Node<T> right;

  public Node(T value) {
    this.value = value;
  }
}

Write this method:

public static <T extends Comparable<T>> boolean isMinHeap(Node<T> root) {

}

An empty tree is valid. Duplicate values are allowed, because a priority queue allows them.

Recall the two properties from the priority queue chapter. The structure property says the tree is complete: every level is full except possibly the last, and the last level is filled from the left. The order property says every node has priority at least as high as its children. For a min-heap, that means no node holds a value larger than either of its children.

A tree can satisfy either property and fail the other, so the method has to check both.

Example 1: This tree is a valid min-heap.

               ╭───╮
               │ 1 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 3 │               │ 2 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 5 │     │ 4 │      │ 8 │
╰───╯     ╰───╯      ╰───╯

The first two levels are full, the last level is filled from the left, and no node is larger than its children.

Example 2: This tree is complete, but it is not a min-heap.

               ╭───╮
               │ 1 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 3 │               │░2░│
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 5 │     │ 4 │      │░0░│
╰───╯     ╰───╯      ╰───╯

It has the same shape as Example 1, so the structure property holds. But 0 is smaller than its parent 2, so the order property fails at the two shaded nodes.

Example 3: This tree keeps the order property, but it is not a min-heap.

            ╭───╮
            │ 1 │
            ╰─┬─╯
      ┌───────┴───────┐
    ╭─┴─╮           ╭─┴─╮
    │ 3 │           │ 2 │
    ╰─┬─╯           ╰─┬─╯
  ┌───┘           ┌───┘
╭─┴─╮           ╭─┴─╮
│ 5 │           │ 8 │
╰───╯           ╰───╯

The last level is not filled from the left: 3 has no right child, but 2 has a left child. If you check each node on its own, every node passes, because no node has a right child without a left child. You only find the problem when you compare nodes across the level.

Your method should run in $O(n)$ time.

For the order property, which pairs of nodes do you have to compare? For the structure property, how do you compare nodes across a level, when each node only knows its own children?

Try it before reading the solution.