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

binTree makeLeaf(int x){
	binTree T = (binTree) malloc(sizeof(binTreeNode));
	T->info = x;
	T->left = NULL;
	T->right = NULL;
    return T;
}

binTree makeBinTree(int x, binTree L, binTree R){
	binTree T= makeLeaf(x);
	T->left = L;
	T->right = R;
    return T;
}

binTree emptyBinTree(){
	return NULL;
}

int isEmptyBinTree(binTree T, int* r, binTree* L, binTree* R){
    if (!T) return 1;
    *L = T->left;
    *R = T->right;
    *r = T->info;
    return 0;
}


int find(int v[], int x, int n){
	int i;
	for (i=0; i<n; i++) if (v[i]==x) return i;
	return -1;
}

binTree binTreeFromVisits(int preorder[], int inorder[], int n){
	binTree T;
	int p,l,r;
	if (n<=0) return NULL;
	p=find(inorder, preorder[0], n);
	return makeBinTree(preorder[0], binTreeFromVisits(preorder+1, inorder, p),
                binTreeFromVisits(preorder+p+1, inorder+p+1, n-p-1));
}

void printBinTree(binTree B){
	int r;
	binTree L,R;
    if (isEmptyBinTree(B,&r,&L,&R)) printf("#");
	else if (!L && !R) printf("%d",r);
	else {
		printf("%d(",r);
		printBinTree(L);
		printf(", ");
		printBinTree(R);
		printf(")");	
		}	
	}