/* Copyleft: Ming Lin <minggr@gmail.com> */

struct node {
	struct node *left, *right;
	int data;
	int distance;
};

struct traversal {
	int *preorder;
	int *inorder;
	int pre_s, pre_e;
	int in_s, in_e;
};

#define NUM 8

int search(int *order, int d)
{
	int i;

	for (i = 0; i < NUM; i++)
		if (order[i] == d)
			break;

	return i;
}

struct node *create(int d)
{
	struct node *n;

	n = malloc(sizeof(*n));
	n->data = d;

	return n;
}

struct node *construct(int preorder[], int inorder[], int pre_s, int pre_e, int in_s, int in_e)
{
	struct node *l_root, *r_root;
	struct node *n;
	int l_len, r_len;
	int i;	

	n = create(preorder[pre_s]);
	i = search(inorder, preorder[pre_s]);
	l_len = i - in_s;
	r_len = in_e - i;
	if (l_len == 0)
		l_root = NULL;
	else
		l_root = construct(preorder, inorder, pre_s+1, pre_s+l_len, in_s, i-1);

	if (r_len == 0)
		r_root = NULL;
	else
		r_root = construct(preorder, inorder, pre_s+l_len+1, pre_e, i+1, in_e); 

	n->left = l_root;
	n->right = r_root;

	return n;
}

#define QUEUE_LEN 10
struct node *queue[QUEUE_LEN];
int head = 0, tail = 0;

void enqueue(struct node *n)
{
	queue[tail] = n;
	tail = (tail+1)%QUEUE_LEN;
}

struct node *dequeue()
{
	struct node *n;

	n = queue[head];
	head = (head+1)%QUEUE_LEN;
	return n;
}

void print_tree(struct node *n)
{
	int num1 = 0;
	int num2 = 0;

	enqueue(n);
	num1++;
	while (n = dequeue()) {
		printf("%d ", n->data);

		if (n->left) {
			enqueue(n->left);		
			num2++;
		}
		if (n->right) {
			enqueue(n->right);		
			num2++;
		}

		num1--;
		if (!num1) {
			printf("\n");
			num1 = num2;
			num2 = 0;
		}
		
	}
}

int is_bst(struct node *n, int parent_data, int is_left)
{
	if (!n)
		return 1;

	if (is_left==1 && n->data > parent_data)
		return 0;
	if (is_left==0 && n->data < parent_data)
		return 0;

	return is_bst(n->left, n->data, 1)
		&& is_bst(n->right, n->data, 0);
}

int first(int postorder[], int s, int e)
{
	int i;

	for (i = s; i < e; i++)
		if (postorder[i] > postorder[e])
			break;

	return i;
}

struct node *construct_bst(int postorder[], int s, int e)
{
	struct node *n;		
	struct node *left, *right;
	int i;

	n = create(postorder[e]);
	i = first(postorder, s, e);
	if (i == s)
		left = NULL;
	else
		left = construct_bst(postorder, s, i-1);

	if (i == e)
		right = NULL;
	else
		right = construct_bst(postorder, i, e-1);

	n->left = left;
	n->right = right;
	return n;
}

int is_max(int postorder[], int s, int e)
{
	int i;

	for (i = s; i < e; i++)
		if (postorder[i] > postorder[e])
			return 0;
	return 1;
}

int is_min(int postorder[], int s, int e)
{
	int i;

	for (i = s; i < e; i++)
		if (postorder[i] < postorder[e])
			return 0;
	return 1;
}

int is_bst_preorder(int postorder[], int s, int e)
{
	int i;
	int r;

	i = first(postorder, s, e);
	if (i == s)
		r = is_min(postorder, s, e);
	else
		r = is_bst_preorder(postorder, s, i-1);

	if (!r)
		return 0;

	if (i == e)
		r = is_max(postorder, s, e);
	else
		r = is_bst_preorder(postorder, i, e-1);

	if (!r)
		return 0;

	return 1;
}

#if 0
int main()
{
	struct node *root;
	int preorder[] = {5,20,1,3,4,7,6,8};
	int inorder[] =  {1,20,3,4,5,6,7,8};
	int pre_s, in_s;
	int pre_e, in_e;
	int postorder[] = {5,7,6,9,11,10,8};

	pre_s = in_s = 0;
	pre_e = in_e = 7;
	root = construct(preorder, inorder, pre_s, pre_e, in_s, in_e);

	//print_tree(root);

	root = construct_bst(postorder, 0, 6);
	print_tree(root);
	printf("is_bst(): %d\n", is_bst(root, -1, -1));

	printf("is_bst_preorder(): %d\n", is_bst_preorder(postorder, 0, 6));

	return 0;
}
#endif