Recursion under a heap class-CodePudding

I am trying to solve the following problem.

"Define a recursive method named inOrderTraverse under the Heap class to perform inorder traversal over the nodes in the heap."

In the above problem, Do I convert the heap array to BST to run In order Traversal or Can I perform In order traversal over a heap array using recursion? if so How? Any other different insights on the problem will also be helpful.

If you want to check the whole code,

CodePudding user response：

The problem is that your function is printing heapArr[2*pos], which evidently means it can only ever print data at even indices.

Instead the function should have as goal to print the value of the given pos and of its subtrees.

This also means you need to change the stop condition: it should just verify that pos is a valid index (in range).

So:

public void inOrderTraversal(int pos){
    if (pos > currentSize) {
        return;
    } else {
        inOrderTraversal(2 * pos);
        System.out.print(heapArr[pos]   " " );
        inOrderTraversal(2 * pos   1);
    }
}