Given the level order traversal of a complete binary tree in an array, how to store the inorder traversal of the said tree in the given array, without building up the tree. This is what I came up with.
void recurse (int *inp, int size_array, int *output, int iter_a, int &iter_b)
{
if (iter_a>=size_array)
return;
recurse (inp,size_array,output,2*iter_a+1,iter_b);
output[iter_b] = inp[iter_a];
iter_b++;
recurse (inp,size_array,output,2*iter_a+2,iter_b);
}
Is there an in-place non-recursive O(n) solution for the said problem?