//이게 ㄹㅇ 고통
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int val;
	struct node* lnext;
	struct node* rnext;
}node;

void givelchild(node *, int);
void giverchild(node *, int);
int find(node * ,int);

int main()
{
	int a;
	node head;
	head.val=1;
	head.lnext=NULL;
	head.rnext=NULL;
	givelchild(&head,2);
	giverchild(&head,3);
	givelchild(head.lnext,4);
	giverchild(head.rnext,5);
	scanf("%d",&a);
	printf("%d ",find(&head,a));
	return 0;
}

void givelchild(node * target, int newval)
{
	node * newnode=(node *)malloc(sizeof(node));
	newnode->val=newval;
	target->lnext=newnode;
	newnode->lnext=NULL;
	newnode->rnext=NULL;
}

void giverchild(node * target, int newval)
{
	node * newnode=(node *)malloc(sizeof(node));
	newnode->val=newval;
	target->rnext=newnode;
	newnode->lnext=NULL;
	newnode->rnext=NULL;
}

int find(node * target,int findint)
{
	int flag=0;
	if(target->val==findint) return 1;
	if(target->lnext==NULL && target->rnext==NULL) return 0;
	if(target->lnext!=NULL) flag+=find(target->lnext,findint);
	if(target->rnext!=NULL) flag+=find(target->rnext,findint);
	if(flag==0) return 0;
	else return 1;
}

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


typedef struct node{
	char v;
	struct node* Lnode;
	struct node* Rnode;
}node;

typedef struct Qnode{
	node* v;
	struct Qnode* next;
}Qnode;

void Lpush(node*, char*);
void Rpush(node*, char*);
void Lpop(node*);
void Rpop(node*);
int find(node*, char*);
int bfs(node*, char*);
void QLpush(Qnode*);
void QRpush(Qnode*);

void main(){

	node hd = { NULL };
	int num;
	char val;
	hd.v = 'e';
	Lpush(&hd, 'c');
	Lpush(hd.Lnode, 'd');
	Rpush(hd.Lnode->Lnode, 'f');
	Rpush(&hd, 'b');
	Rpush(hd.Rnode, 'a');

	val = 'a';

	printf("------------------bfs----------------\n");
	if (bfs(&hd, &val) == 1){
		printf("없음\n");
	}
	else{
		printf("있음\n");
	}

	printf("------------------dfs----------------\n");
	if (find(&hd, &val) == 1){
		printf("없음\n");
	}
	else{
		printf("있음\n");
	}

	printf("-------------free--------------------\n");

	Rpop(hd.Lnode->Lnode);
	Lpop(hd.Lnode);
	Lpop(&hd);
	Rpop(hd.Rnode);
	Rpop(&hd);


}


void Lpush(node* hd, char val){
	node* tmp = (node*)malloc(sizeof(node));

	tmp->v = val;
	tmp->Rnode = NULL;
	tmp->Lnode = NULL;

	hd->Lnode = tmp;
}


void Rpush(node* hd, char val){
	node* tmp = (node*)malloc(sizeof(node));

	tmp->v = val;
	tmp->Rnode = NULL;
	tmp->Lnode = NULL;
	hd->Rnode = tmp;
}


void Lpop(node* hd){
	char a;
	a = hd->Lnode->v;
	printf("%c\n", a);
	free(hd->Lnode);
	hd->Lnode = NULL;
}


void Rpop(node* hd){
	char a;
	a = hd->Rnode->v;
	printf("%c\n", a);
	free(hd->Rnode);
	hd->Rnode = NULL;
}

int find(node* hd, char* val){

	
	if (hd->Lnode != NULL){
		if (find(hd->Lnode, val) == 0){
			printf("%c\n", hd->Lnode->v);
			return 0;
		}
		printf("%c\n", hd->Lnode->v);
	}


	if (hd->Rnode != NULL){
		if (find(hd->Rnode, val) == 0){
			printf("%c\n", hd->Rnode->v);
			return 0;
		}

		printf("%c\n", hd->Rnode->v);
	}

	if (hd->v == *val){
		return 0;
	}


	return 1;
}

int bfs(node* hd, char *val){
	Qnode* Qhd = (Qnode*)malloc(sizeof(Qnode));
	Qhd->next = NULL;
	Qhd->v = hd;

	while (Qhd->v != NULL){
		if (Qhd->v->v == *val){
			printf("%c\n", Qhd->v->v);
			return 0;
		}
		else{
			QLpush(Qhd);
			QRpush(Qhd);
			printf("%c\n", Qhd->v->v);
			Qhd = Qhd->next;
			
		}
		
	}
	
	return 1;
}
void QLpush(Qnode* Qhd){
	if (Qhd->v->Lnode != NULL){
		Qnode* tmp3 = (Qnode*)malloc(sizeof(Qnode));
		tmp3->next = NULL;
		tmp3->v = Qhd->v->Lnode;
		while (Qhd->next != NULL){
			Qhd = Qhd->next;
		}
		Qhd->next = tmp3;
	}
	
}
void QRpush(Qnode* Qhd){
	if (Qhd->v->Rnode != NULL){
		Qnode* tmp3 = (Qnode*)malloc(sizeof(Qnode));
		tmp3->next = NULL;
		tmp3->v = Qhd->v->Rnode;
		while (Qhd->next != NULL ){
			Qhd = Qhd->next;
		}
		Qhd->next = tmp3;
	}

}