CareerCup

Since this is a complete binary tree, you can simulate the inorder traversal by noting the following properties:

INPUT:
Array[N] - array of the level-order traversal of a complete binary tree

NOTES:
1. Left child node of the node with index "nidx": lidx = 2*nidx - 1
2. Right child node of the node with index "nidx": ridx = 2*nidx + 2
3. The parent node's index of the node with index "nidx": pidx = (nidx - 1) / 2 // integer division

Below is the iterative version of the suggested approach:

#include <stdio.h>
#include <stack>

using std::stack;

static int N = 15;

int left(const int& nidx)
{
    int rv = 2 * nidx + 1;
    if (rv >= N)
        rv = -1;    
    return rv;
}

int right(const int& nidx)
{
    int rv = 2 * nidx + 2;
    if (rv >= N)
        rv = -1;    
    return rv;
}

int parent(const int& nidx)
{
    if (0 == nidx)
        return -1;
        
    int rv = (nidx - 1) / 2;
    if (rv < 0)
        rv = -1;    
    return rv;
}

void iter_inorder()
{
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    stack<int> S;
    
    for (int i = 0; i < N; ++i){
        int lidx, ridx, pidx;
        lidx = left(i);
        ridx = right(i);
        pidx = parent(i);
        
        printf("NIDX: %-3d LIDX: %-3d  RIDX: %-3d  PIDX: %-3d\n", 
                i, lidx, ridx, pidx);
    }
    
    printf("\n\n");
    
    int current = 0;
    S.push(current);
    
    while (!S.empty()){
        while (current != -1){
            current = left(current);
            
            if (-1 != current) {
                printf("pushing: %d\n", current);
                S.push(current);
            }   
        }
        
        current = S.top();
        S.pop();
        printf("IDX: %-3d NUM: %-3d\n", current, arr[current]);
        
        current = right(current);
        if (-1 != current)
            S.push(current);
    }
}

int main()
{
    iter_inorder();
    return 0;
}

And this is the output of the run:

NIDX: 5   LIDX: 11   RIDX: 12   PIDX: 2
NIDX: 6   LIDX: 13   RIDX: 14   PIDX: 2
NIDX: 7   LIDX: -1   RIDX: -1   PIDX: 3
NIDX: 8   LIDX: -1   RIDX: -1   PIDX: 3
NIDX: 9   LIDX: -1   RIDX: -1   PIDX: 4
NIDX: 10  LIDX: -1   RIDX: -1   PIDX: 4
NIDX: 11  LIDX: -1   RIDX: -1   PIDX: 5
NIDX: 12  LIDX: -1   RIDX: -1   PIDX: 5
NIDX: 13  LIDX: -1   RIDX: -1   PIDX: 6
NIDX: 14  LIDX: -1   RIDX: -1   PIDX: 6


pushing: 1
pushing: 3
pushing: 7
IDX: 7   NUM: 7
IDX: 3   NUM: 3
IDX: 8   NUM: 8
IDX: 1   NUM: 1
pushing: 9
IDX: 9   NUM: 9
IDX: 4   NUM: 4
IDX: 10  NUM: 10
IDX: 0   NUM: 0
pushing: 5
pushing: 11
IDX: 11  NUM: 11
IDX: 5   NUM: 5
IDX: 12  NUM: 12
IDX: 2   NUM: 2
pushing: 13
IDX: 13  NUM: 13
IDX: 6   NUM: 6
IDX: 14  NUM: 14

Inorder traversal produces a sorted list in a BST, so just sort the given list to produce the Inorder traversal.