#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void err()
{
	printf("Error\n");
}

struct Node
{
	char * number;
	char * name;
	struct Node * l;
	struct Node * r;
	struct Node * p;
};

struct Node * root;
int size;

void inic(char * name, char * number)
{
	root = malloc(sizeof(struct Node));
	root->name = name;
	root->number = number;
	root->l = NULL;
	root->r = NULL;
	root->p = NULL;
	size = 1;
}
void rec_add(struct Node * cur_vertex, char * name, char * number)
{
	int cmp = strcmp(name, cur_vertex->name);
	if(cmp==-1)
	{
		if(cur_vertex->l == NULL)
		{
			struct Node * new_vertex = malloc(sizeof(struct Node));
			new_vertex->name = name;
			new_vertex->number = number;
			new_vertex->p = cur_vertex;
			cur_vertex->l = new_vertex;
			new_vertex->l = NULL;
			new_vertex->r = NULL;
			size++;
		}
		else
		{
			rec_add(cur_vertex->l, name, number);
			return;
		}
	}
	else
	{
		if(cur_vertex->r == NULL)
		{
			struct Node * new_vertex = malloc(sizeof(struct Node));
			new_vertex->name = name;
			new_vertex->number = number;
			new_vertex->p = cur_vertex;
			cur_vertex->r = new_vertex;
			new_vertex->l = NULL;
			new_vertex->r = NULL;
			size++;
		}
		else
		{
			rec_add(cur_vertex->r, name, number);
			return;
		}
	}
}
void add(char * name, char * number)
{
	if(size == 0)
	{
		inic(name, number);
	}
	else
	{
		rec_add(root, name, number);
	}
}

void rec_del(struct Node * cur_vertex, char * name)
{
	int cmp = strcmp(cur_vertex->name, name);
	if(cmp==1)
	{
		if(cur_vertex->l == NULL)
		{
			err();
			return;
		}
		else
		{
			rec_del(cur_vertex->l, name);
			return;
		}
	}
	else if(cmp==-1)
	{
		if(cur_vertex->r == NULL)
		{
			err();
			return;
		}
		else
		{
			rec_del(cur_vertex->r, name);
			return;
		}
	}

	if(cur_vertex->l==NULL&&cur_vertex->r==NULL)
	{
		if(cur_vertex->p != NULL)
		{
			if(cur_vertex->p->l==cur_vertex)
			{
				cur_vertex->p->l = NULL;
			}
			else
			{
				cur_vertex->p->r = NULL;
			}
		}
		else
		{
			free(root);
		}
		free(cur_vertex);
		size--;
		return;
	}

	if(cur_vertex->l==NULL)
	{
		struct Node * d = cur_vertex->r;
		cur_vertex->name = cur_vertex->r->name;
		cur_vertex->number = cur_vertex->r->number;
		cur_vertex->l = d->l;
		cur_vertex->r = d->r;
		if(cur_vertex->r!=NULL)
			cur_vertex->r->p = cur_vertex;
		if(cur_vertex->l!=NULL)
			cur_vertex->l->p = cur_vertex;
		free(d);
		size--;
		return;
	}

	if(cur_vertex->r==NULL)
	{
		struct Node * d = cur_vertex->l;
		cur_vertex->name = cur_vertex->l->name;
		cur_vertex->number = cur_vertex->l->number;
		cur_vertex->l = d->l;
		cur_vertex->r = d->r;
		if(cur_vertex->r!=NULL)
			cur_vertex->r->p = cur_vertex;
		if(cur_vertex->l!=NULL)
			cur_vertex->l->p = cur_vertex;
		free(d);
		size--;
		return;
	}

	struct Node * K =  cur_vertex->l;
	while(K->r!=NULL)
		K = K->r;
	cur_vertex->name = K->name;
	cur_vertex->number = K->number;

	if(K->p == cur_vertex)
	{
		cur_vertex->l = K->p->l;
		K->p->l->p = cur_vertex;
		free(K);
		size--;
	}
	else
	{
		K->p->r = K->l;
		K->l->p = K->p;
		free(K);
		size--;
	}
}

void erase(char * name)
{
	if(size>0)
	{
		rec_del(root, name);
	}
	else
	{
		err();
		return;
	}
}

void rec_find(struct Node * cur,char * name)
{
	int cmp = strcmp(cur->name, name);
	if(cmp == 0)
	{
		printf("Number of %s is %s\n", name, cur->number);
		return;
	}
	if(cmp==1)
	{
		if(cur->l==NULL)
		{
			err();
			return;
		}
		else
		{
			rec_find(cur->l, name);
		}
	}
	else
	{
		if(cur->r==NULL)
		{
			err();
			return;
		}
		else
		{
			rec_find(cur->r, name);
		}
	}
}

void find(char * name)
{
	if(size==0)
	{
		err();
		return;
	}
	else
	{
		rec_find(root, name);
	}
}

void rec_bypass(struct Node * cur_vertex)
{
	if(cur_vertex->l !=NULL)
	{
		rec_bypass(cur_vertex->l);
	}

	printf("%s %s\n", cur_vertex->name, cur_vertex->number);

	if(cur_vertex->r!=NULL)
	{
		rec_bypass(cur_vertex->r);
	}


}

void bypass()
{
	if(size>0)
	{
		rec_bypass(root);
	}
	else
	{
		err();
		return;
	}
}

char * readString()
{
	char * a = malloc(sizeof(char)*25);
	for (int i=0; i<25; i++)
	{
		a[i]=' ';
	}
	char ch = getchar();
	for (int i=0; i<25; i++)
	{
		if(ch!=' '&&ch!='\n'&&ch!='\0'&&ch!=EOF)
		{
			a[i]=ch;
			ch = getchar();
		}
	}
	return a;
}
void print(char * a)
{
	for (int i=0; i<25; i++)
	{
		putchar(a[i]);
	}
	printf("\n");
}
int main()
{
	size = 0;
	// add (name + number)
	// erase(name)
	// find (name)
	// bypass()
	return 0;
}