Solution: Checking Completeness

Example 3 showed that completeness cannot be checked one node at a time. Here is that tree again:

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

3 is missing its right child, and 2 has a child further along the same level. To see that, the check has to read the tree across each level.

Reading the tree in level order

The tree chapter has a traversal that reads a tree one level at a time: level order. It visits the nodes top to bottom, and left to right within each level, and it keeps the nodes waiting to be visited in a queue.

Now list the child slots in the same order: the root’s left and right, then each child’s left and right, and so on. In a complete tree, every filled slot comes before every empty slot.

So the check is: traverse the tree in level order, and remember whether we have passed an empty child slot. If we find a node after that, the tree is not complete.

private static <T> boolean isComplete(Node<T> root) {
  if (root == null) {
    return true;
  }
  Queue<Node<T>> queue = new LinkedQueue<>();
  queue.enqueue(root);
  boolean gap = false;  // have we passed a missing child yet?
  while (!queue.isEmpty()) {
    Node<T> node = queue.front();
    queue.dequeue();
    if (node.left == null) {
      gap = true;
    } else if (gap) {
      return false;  // a node after a missing child
    } else {
      queue.enqueue(node.left);
    }
    if (node.right == null) {
      gap = true;
    } else if (gap) {
      return false;  // a node after a missing child
    } else {
      queue.enqueue(node.right);
    }
  }
  return true;
}

The loop is the level-order traversal from the tree chapter, with the gap check added at each child slot. We never enqueue null, because our enqueue rejects it.

Tracing it on Example 3

Start with 1 in the queue, and gap set to false:

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

queue:

┌───┐
│ 1 │
└───┘
  ▲
front, back

gap = false

Take 1 from the front. Its left child 3 and right child 2 both exist, and there is no gap yet, so both go in the queue:

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

queue:

┌───┬───┐
│ 3 │ 2 │
└───┴───┘
  ▲   ▲
front back

gap = false

Take 3 from the front. Its left child 5 goes in the queue. Its right child is missing, so gap becomes true:

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

queue:

┌───┬───┐
│ 2 │ 5 │
└───┴───┘
  ▲   ▲
front back

gap = true

Take 2 from the front. Its left child 8 exists, but gap is already true, so isComplete returns false:

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

queue:

┌───┐
│ 5 │
└───┘
  ▲
front, back

gap = true

On Example 1, the first missing slot is the right child of 2. Every node left in the queue after that is a leaf, so no node comes after the gap, and isComplete returns true.

The cost

The level-order traversal visits each node at most once and does a constant amount of work per visit, so isComplete is $O(n)$. isOrdered is $O(n)$ too, so isMinHeap is $O(n)$.

The queue holds the nodes waiting to be visited. At one point it holds the whole bottom level, and the bottom level of a complete tree can hold about half of its nodes. So the extra space is $O(n)$. The recursion in isOrdered also uses space, one call frame per level, and on a tree where every node has at most one child that is $n-1$ levels.