#include <iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
using std::cin;
using std::endl;
using std::cout;

struct node
{
	int info;
	node *l, *r;
};

node *root=NULL;
/*//Ф-я запису елемента в дерево*/
void push(char a,node **t)
{
    if ((*t)==NULL) //якщо дерева не існує
    {
        (*t)=new node; //виділяємо пам*ять
        (*t)->info=a; //Кладемо в виділене місце елемент а
        (*t)->l=(*t)->r=NULL; //очищуємо пам*ять для наступного росту
        return; //виходимо
    }
       //дерево є
        if (a>(*t)->info) push(a,&(*t)->r); //якщо елемент більше ніж наступний кладемо його вправо
        else push(a,&(*t)->l); //інакше кладемо вліво
}

/*відображаємо дерево на екрані*/
void print (node *t) 
{	
	if (t) 
	{ 
	print(t->l); 
	if (t->info) cout<< t->info<<' '; 
	print(t->r); 
	} 
    /*if (t==NULL) return; //якщо пусте Дерево то немає чого відображати
    else //інакше
    print(root->l);
    if(root->info)
    cout<<root->info;
    print(root->r);
    //за допомогою рекурсії ідемо в праве піддерево
	*/
}
void Delete (node **d, int k) 
{ 
	node *q; 
	if (*d == NULL) cout<< "No such key\n"; 
	else 
	if (k<(**d).info) Delete(&((**d).l), k); 
	else 
	if (k>(**d).info) Delete(&((**d).r), k); 
	else { 
	q = *d; 
	if ((*q).r == NULL) { *d = (*q).l; delete q; } 
	else 
	if ((*q).l == NULL) { *d = (*q).r; delete q; } 
	} 
}
int main ()
{   
 	int A[]={1,2,3,4,5};
 	cout<<"Our digits:\n";
    for (int i=0;i<5;++i)
    {
    cout<<A[i]; //виводимомо елемент за елементом
    push(A[i],&root); //кожний елемент кладемо в дерево
    }
    cout<<" Our tree:\n";
    print(root);
    Delete(&root,4); 
	cout << '\n'; 
	cout << "tree 2\n"; 
	print(root); 
    getch();       
}