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

int big_deep;

typedef struct Tree
{
  int key;
  int length_sons;
  struct Tree* parent;
  struct Tree* *sons;
}node;

void create_tree(node **tree, int key)
{
	node *tmp_tree = malloc(sizeof(node));
	tmp_tree->key = key;
	tmp_tree->length_sons = 0;
	tmp_tree->parent = NULL;
	tmp_tree->sons = NULL;
	*tree = tmp_tree;
}

node* find_leaf(node **tree, int leaf) {
	node *work_tree = *tree;

	if(work_tree == NULL) return NULL;

	if(work_tree->key == leaf) return work_tree;

	node *where = NULL;
	if(work_tree->sons) {
	  int length = work_tree->length_sons;
	  for(int i=0; i<length; i++) {
	  	where = find_leaf(&work_tree->sons[i], leaf);
		if( (where) && (where->key == leaf) ) return where;
	  }
	}
	return work_tree;
}

void add_node(node **tree, int key, int father)
{
	node *work_tree = find_leaf(tree, father);
	node *tmp_node = malloc(sizeof(node));
	tmp_node->key = key;
	tmp_node->length_sons = 0;
 	tmp_node->parent = work_tree;
	tmp_node->sons = NULL;
	if(work_tree->sons){
	  int length = work_tree->length_sons;
	  work_tree->sons[length] = tmp_node;
	  work_tree->length_sons+=1;
	}
	else {
	  work_tree->sons = malloc(sizeof(node));
	  work_tree->sons[0] = tmp_node;
	  work_tree->length_sons+=1;
	}
}

void delete_node(node **tree, int key)
{
	node *work_tree = find_leaf(tree, key);
	if(work_tree->length_sons > 0) {
	  int length = work_tree->length_sons;
	  for(int i = (length-1); i>=0 ; i-- ) delete_node(&work_tree->sons[i], work_tree->sons[i]->key);
	  length--;
	}
	node *parent_tree = work_tree->parent;
	if(parent_tree != NULL) {
	  int length = parent_tree->length_sons;
	  int position = -1;
	  for(int i=0; i<length; i++) {
	  	if(parent_tree->sons[i]->key == key) position = i;
	  }
	  if(position < (length-1) ) {
	    for(int i = (position+1) ; i < length ; i++ ){
	    	parent_tree->sons[i-1] = parent_tree->sons[i];
	    }
	  }
	  parent_tree->sons[length-1] = NULL;
	  parent_tree->length_sons = length-1;
	}
	free(work_tree);
	work_tree = NULL;
}

void print_tree(node *tree, int space)
{
	if(tree != NULL) {
	  for(int i=0;i<space;i++) printf(" ");
	  printf("%d\n", tree->key);
	  if(tree->sons != NULL) {
	    int length = tree->length_sons;
	    for(int i=0;i<length;i++) {
	    	print_tree(tree->sons[i], (space+1));
	    }
	  }
	}
}

void find_deep(node *tree, int current_deep)
{
	if(tree != NULL) {
	  if(current_deep > big_deep) big_deep = current_deep;
	  if(tree->sons != NULL) {
	    int length = tree->length_sons;
	    for(int i=0;i<length;i++) {
	    	find_deep(tree->sons[i], (current_deep+1));
	    }
	  }
	}
}

void print_menu()
{
	printf("_^_^_^_^_^_^_\n");
	printf("Menu:\n1. Add node;\n2. Print tree;\n3. Delete node;\n4. Deep tree.\nChoose one action: \n");
}

int main(void) {
   node* tree = NULL;

   int inp, key, key_start, father;
   print_menu();
   while(scanf("%d", &inp)!=EOF) {
   	switch(inp) {
	  case 1:
	  	printf("Input node: ");
	  	scanf("%d", &key);
		if(tree == NULL) {
		  key_start = key;
		  create_tree(&tree, key);
                }
		else {
		  printf("\nInput father: ");
	  	  scanf("%d", &father);
		  add_node(&tree, key, father);
	 	}
		break;
	  case 2:
		if(tree == NULL) printf("\nTree is empty.\n");
		else {
		  printf("_\n");
		  print_tree(tree, 0);
		  printf("_\n");
		}
		break;
	  case 3:
		if(tree == NULL) printf("\nNo tree, no delete.\n");
		else {
		  printf("Input node: ");
	  	  scanf("%d", &key);
		  delete_node(&tree, key);
		  if(key == key_start) tree = NULL;
		}
		break;
	  case 4:
		if(tree == NULL) printf("\nNo tree, no deep.\n");
		else {
		  big_deep = 0;
	  	  find_deep(tree, big_deep);
		  printf("Tree deep is %d\n", big_deep);
                }
		break;
	}
   	print_menu();
   }

   return 0;
}