/*Napisati funkciju za uređivanje proizvoljnog binarnog stabla celih brojeva u binarno stablo za pretragu
korišćenjem SelectionSort algoritma (uzastopni izbor minimuma), bez korišćenja pomoćnih struktura
podataka. Čvorovi binarnog stabla sadrže samo podatak i pokazivače na potomke.
sa pravljenjem novog stabla - 10 poena
bez pravljenja novog stabla - 20 poena*/

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

#define novo(x) x=(drvo *) malloc (sizeof(drvo))

typedef struct drvo
{
	int broj;
	struct drvo *levi;
	struct drvo *desni;
} drvo;

void dodaj(drvo **p,int broj)
{
		drvo *temp;
		novo(temp);
		if (!temp)
		{
			printf("alok");
			exit(1);
		}
		temp->broj=broj;
		temp->levi=NULL;
		temp->desni=NULL;
		drvo *p1=*p;
		if (!p1)
		{
			*p=temp;
			return;
		}
		drvo *p2=NULL;
		while(p1)
		{
			p2=p1;
			if (broj>=p1->broj) p1=p1->levi;
			else p1=p1->desni;
		}
		if (p2->broj<=broj) p2->levi=temp; else p2->desni=temp;
}



drvo *formiraj()
{
	int n,i,broj;
	drvo *p=NULL;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&broj);
		dodaj(&p,broj);
	}
	return p;
}

void ispis(drvo *p)
{
		if (p->levi) ispis(p->levi);
		printf("%3d",p->broj);
		if (p->desni) ispis(p->desni);
}

void pronadjimin(drvo *p,drvo **min,drvo **min1)
{
		if (!p) return;
		drvo *mini=*min;
		if (p->levi)
		{
			if (p->levi->broj<mini->broj)
			{
				*min=p->levi;
				*min1=p;
			}
			pronadjimin(p->levi,min,min1);
		}
		if (p->desni)
		{
			if (p->desni->broj<mini->broj)
			{
				*min=p->desni;
				*min1=p;
			}
			pronadjimin(p->desni,min,min1);
		}
}

void ubaci(drvo **p,drvo *temp)
{
		temp->levi=NULL;
		temp->desni=NULL;
		drvo *p1=*p;
		if (!p1)
		{
			*p=temp;
			return;
		}
		drvo *p2=NULL;
		while(p1)
		{
			p2=p1;
			if (p1->broj>=temp->broj) p1=p1->levi;
			else p1=p1->desni;
		}
		if (p2->broj>=temp->broj) p2->levi=temp; else p2->desni=temp;
}

void izbaci(drvo **p,drvo *min,drvo *min1)
{
	drvo *pom;
	if ( min->levi && min->desni && min1 )
	{
		min1->levi=min->levi;
		pom=min->desni;
		while(pom->desni)
		pom=pom->desni;
		pom->desni=min->desni;
	}
	else if (min->levi && min->desni)
	{
			*p=min->levi;
			pom=min->levi;
			while(pom->desni)
			pom=pom->desni;
			pom->desni=min->desni;
	}
	else if (min->desni && (!min1))
	{
			*p=min->desni;
	}
	else if (min->levi && (!min1))
	{
			*p=min->levi;
	}
	else if (min->levi && min1)
	{
			if (min1->levi==min)
			{
				min1->levi=min->levi;
			}
			else
			{
				min1->desni=min->levi;
			}
	}
	else if (min->desni && min1)
	{
			if (min1->desni==min)
			{
				min1->desni=min->desni;
			}
			else
			{
				min1->levi=min->desni;
			}
	}
	else if ( (! min->desni) && (! min->levi) && (min1))
	{
			if (min==min1->levi) min1->levi=NULL; else min1->desni=NULL;
	}
	else *p=NULL;
}

main()
{
		drvo *p,*min,*min1,*q=NULL;
		p=formiraj();
		if (p) ispis(p);
		while(p)
		{
			min=p; min1=NULL;
			pronadjimin(p,&min,&min1);
			izbaci(&p,min,min1);
			ubaci(&q,min);
		}
		ispis(q);
}