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

typedef struct N
{
    int key;
    struct N *left;
    struct N *right;
} Node;


typedef struct stack
{
    Node *treeNode;
    struct stack *next;
} stackNode;

Node *CreateBalanced (int N);
void inorder (Node *root);
int isEmpty(stackNode *top);
void push (stackNode **top, Node *v);
void deleteStack(stackNode **top);
void printinOrder ( Node *root);

int main()
{
    Node *root = NULL;
    int n,nr1,nr2;

    printf("numarul de noduri=");
    scanf("%d",&n);
    root = CreateBalanced(n);
  //  printinOrder(root);
    inorder(root);

    return 0;
}


Node *CreateBalanced (int N)
{
    int toAdd;
    if(N>0)
    {
        Node* root = (Node*)malloc(sizeof(Node));
        printf("valoare nod=");
        scanf("%d",&toAdd);
        root->key = toAdd;

        root->left = CreateBalanced(N/2);
        root->right = CreateBalanced(N-1-N/2);
        return root;
    }
    else
        return NULL;
}

void push (stackNode **top, Node *v)
{
    stackNode* newNode = (stackNode*)malloc(sizeof(Node));
    newNode->treeNode = v;
    newNode->next = *top;
    *top = newNode;
}

Node* pop(stackNode **top)
{
    if(isEmpty(*top))
        return NULL;
    stackNode *temp = (*top);
    Node *aux = temp->treeNode;
    *top = (*top)->next;
    free(temp);
    return aux;
}

int isEmpty(stackNode *top)
{
    return top == NULL;
}

void inorder (Node *root)
{
    stackNode *S = NULL;
    while(1)
    {
        while(root)
        {
            push(&S,root);
            root = root->left;
            printf("%d",root->key);
        }


        if(isEmpty(S))
            break;
        root = pop(&S);
        printf("%d",S->treeNode->key);
        root = root->right;
    }
    deleteStack(&S);
}

void deleteStack(stackNode **top)
{
    stackNode* topCopy = *top, *temp;
    while(topCopy !=  NULL)
    {
        temp = topCopy;
        topCopy = topCopy->next;
        //printf("%d",temp->key);
        free(temp);
    }
    *top = NULL;
}

void printinOrder ( Node *root)
{
    if(root == NULL)
        return;
    printinOrder(root->left);
    printf("%d  ",root->key);
    printinOrder(root->right);

}