generate binary tree from pre and in order

binaryTree_pre-in-generation.c

#include "stdio.h"

void postorder(int idx, int vals[], int left[], int right[]){
    if(left[idx]>-1){ postorder(left[idx], vals, left, right); }
    if(right[idx]>-1){ postorder(right[idx], vals, left, right); }
    printf("%d ", vals[idx]);
}

int main(void){
    int n; scanf("%d", &n);
    int pre[n], in[n];

    // reading in
    int i;
    for(i=0; i<n; i++){ scanf("%d", &pre[i]); }
    for(i=0; i<n; i++){ scanf("%d", &in[i]); }
    
    // hashtable for indexs
    int idxs[n];
    for(i=0; i<n; i++){ idxs[in[i]] = i; }
    
    // node pointers
    int left[n], right[n];
    for(i=0; i<n; i++){ left[i]=-1; right[i]=-1; }

    // stack of nodes
    int stack[n];
    int stack_ptr = 0;

    // marked toggle
    int marked[n]; for(i=0; i<n; i++){ marked[i]=0; }

    // generating tree from pre and in order 
    for(i=0; i<n; i++){ 
        int curr = idxs[pre[i]];
        
        // if something to act on the the nodes 
        if(stack_ptr){
            int prev = idxs[pre[stack[stack_ptr-1]]];
            
            if(curr<prev){
                printf("%d %d, %d %d\n", prev, pre[stack[stack_ptr-1]], curr, pre[i]);
                left[stack[stack_ptr-1]] = i;
            }else{
                while(marked[prev+1]){
                    stack_ptr--;
                    prev = idxs[pre[stack[stack_ptr-1]]];
                }
                right[stack[stack_ptr-1]] = i;
            }
        }
        
        marked[curr] = 1;
        stack[stack_ptr] = i;
        stack_ptr++;
    }

    // print post order to check
    postorder(0, pre, left, right);

    return 0;
}

test.in

10
7 2 5 6 8 0 4 3 9 1
5 8 6 2 0 7 9 3 1 4

postorder:
8 6 5 0 2 9 1 3 4 7