#include<stdio.h>
#include<malloc.h>

struct node
{
  int data;
  struct node* left;
  struct node* right;
  struct node* next;
};

typedef struct node Node;

void AddNode(Node* root, int number)
{	
	if(root->data==number)
		return;
	else if(root->data>number)
	{
		if(root->left!=NULL)
		{
			AddNode(root->left,number);
		}
		else
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = number;
			newNode->left = NULL;
			newNode->right= NULL;
			newNode->next= NULL;
			root->left = newNode;
		}
	}
	else if(root->data<number)
	{
		if(root->right!=NULL)
		{
			AddNode(root->right,number);
		}
		else
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = number;
			newNode->left = NULL;
			newNode->right= NULL;
			newNode->next= NULL;
			root->right= newNode;
		}
	}
}

int IsMirror(Node* left,Node* right)
{
	if(left==NULL&&right==NULL)
		return 1;
	if(left==NULL||right==NULL)
		return 0;
	return(IsMirror(left->right,right->left)&&IsMirror(left->left,right->right));
}

int IsFoldable(Node* root)
{
	if(root==NULL)
		return 1;
	else
		return IsMirror(root->left,root->right);
}


int main()
{
	Node* root = (Node*)malloc(sizeof(Node));
	root->data = 20;
	root->left = NULL;
	root->right= NULL;
	root->next= NULL;

	AddNode(root,10);
	AddNode(root,5);
	AddNode(root,15);
	AddNode(root,8);
	AddNode(root,30);
	AddNode(root,25);
	AddNode(root,35);
	AddNode(root,32);
	//AddNode(root,10);
	//AddNode(root,3);
	//AddNode(root,4);
	
	
	printf("%d",IsFoldable(root));
 
  return 0;
}