#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
        
    
    Node* reconstructTree(int* arr, int n, int* index){
        if(*index >=n || arr[*index] == 0){
            (*index)++;
            return NULL;
        }
        Node* root = createNode(arr[*index]);
        (*index)++;
        root->left = reconstructTree(arr, n, index);
        root->right = reconstructTree(arr, n,index);
        return root;
        
    }
    
    void preorder(Node* root) {
        if (root) {
            printf("%d ", root->data);
            preorder(root->left);
            preorder(root->right);
        }
    }
    
    void inorder(Node* root) {
        if(root) {
            inorder(root->left);
            printf("%d ",root->data);
            inorder(root->right);
        }
    }
    
        
    void postorder(Node* root){
        if(root){
            postorder(root->left);
            postorder(root->right);
            printf("%d ", root->data);

        }
    }
    
    int main(){
        int arr[] = { 1, 2, 3, 0, 0, 0};
        int n = sizeof(arr)/sizeof(arr[0]);
        int index = 0;
        Node* root = reconstructTree(arr, n, &index);
        printf("Preorder: ") ;preorder(root); printf("\n");
        printf("Ininorder(root); printf("\n");
        postorder(root); printf("\n");
        return 0;
    }