How to preorder traverse a min heap using array indexing

Question

I created a standard min heap class. I am trying to figure out a way to index the values in the min heap in preorder traversal format. The only way I have seen it done is using left and right pointers. But the "nodes" in my array are not nodes just values. Is it possible to do preorder traversal on a min heap array using indexing? If so how?

Answer 1

The left/right links are implicitly available, as the left child of the value at index is to be found at index 2+1 (if within the size of the array), and the right child at index 2+2.

So you can just use the known preorder algorithm and use these formulas for visiting children.

For instance, we could have this min heap:

     _3_
    /   \
   6     4
  / \   /
10   9 5

...which would be encoded in an array as follows:

[3, 6, 4, 10, 9, 5]

The preorder traversal would be:

3 6 10 9 4 5

Here is an implementation in JavaScript that is run for this example:

function preorder(minheap, start) {
    if (start >= minheap.length) return; // all done
    console.log(minheap[start]);
    preorder(minheap, start * 2 + 1); // left child
    preorder(minheap, start * 2 + 2); // right child
}

// Example run:
const minheap = [3, 6, 4, 10, 9, 5];
preorder(minheap, 0);