Question

Write an algorithm that determines whether or not an almost complete binary tree is a heap.

Short answer

The algorithm will go through the binary tree, checking each node to ensure that it meets the properties of a heap (value priority compared to its children and completeness). If any node fails this test, then the binary tree is not a heap.

Step-by-step solution

- Initialization

Start by initializing an empty queue, say \( q \), and push the root of the binary tree into it.

- Heap Validity Check

Next, we dequeue an element from \( q \) and perform the following validations: A. Check whether the dequeued node has a higher priority than its children. In a min heap, node value is less than or equal to children and in a max heap, node value is greater than or equal to children. B. Check that dequeued node preserves completeness of the binary tree. For this, after encountering the first non-full node (a node that does not have both the children), every following node in the level order traversal should be a leaf node.

- Continue Traversal

If the dequeued element has a left child, then push it into the queue. Do the same for its right child if it exists.

- Repeat

Repeat steps 2 and 3 until the queue is empty. If a step ever results in the tree failing the heap validation (step 2), then the tree is not a heap.