#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);
void liberateTreeRecursion (Node *root);
Node *LCA(Node *root, int nr1, int nr2);


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

    printf("numarul de noduri=");
    scanf("%d",&n);
    root = CreateBalanced(n);
    //  printinOrder(root);
    inorder(root);
    printf("\nNumerele pentru care vreti sa calculati LCA:\nNr.1:");
    scanf("%d",&nr1);
    printf("Nr.2:");
    scanf("%d",&nr2);
    lowCommAnc = LCA(root, nr1, nr2);
    printf("\nLCA (%d , %d) = %d",nr1,nr2,lowCommAnc->key);
    liberateTreeRecursion(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)? 1 : 0;
}

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


        if(isEmpty(S))
            break;
        else
        {
            traveler = pop(&S);
            printf("%d ",traveler->key);// !!!
            traveler = traveler->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);
}

void liberateTreeRecursion (Node *root)
{
    if(!root)
        return;
    liberateTreeRecursion(root->left);
    liberateTreeRecursion(root->right);
    free(root);
}

Node *LCA(Node *root, int nr1, int nr2)
{
    Node* lowComAnc;
    if(!root)
        return NULL;

    Node *LCA_L = NULL;
    Node *LCA_R  = NULL;

    LCA_L = LCA(root->left,nr1,nr2);
    LCA_R = LCA(root->right,nr1,nr2);

    if(root->key == nr1)
        return root;
    if(root->key == nr2)
        return root;

    if(LCA_L && LCA_R)
        lowComAnc = root;
    return lowComAnc;

    if(LCA_L)
        return LCA_L;
    if(LCA_R)
        return LCA_R;
    return NULL;

}