program stablo;
type
pokazivac = ^cvor;
cvor = record 
        podatak:integer;
        levo,desno:pokazivac;
        end;
var
koren : pokazivac;
br:integer;
f:Text;
procedure lkd(koren:pokazivac);
begin
if (koren <> nil) then
  begin
  lkd(koren^.levo);
  write(koren^.podatak,' ');
  lkd(koren^.desno);
  end;
end;

procedure dodaj( var koren:pokazivac; br:integer);
begin
if (koren = nil) then
  begin
   new(koren);
   koren^.podatak:=br;
   koren^.levo:=nil;
   koren^.desno := nil;
  end
 else
  begin
   if (koren^.podatak > br) then dodaj(koren^.levo,br)
    else dodaj(koren^.desno,br);
  end;
end;

procedure pronadji(koren:pokazivac;var roditelj,dete:pokazivac;kljuc:integer);
var
pom:pokazivac;
begin

dete:=nil;
roditelj:=nil;

if(koren <> nil) then 
 begin
  
  pom:=koren;
  while ((pom <> nil) and (dete=nil)) do
    begin
     if (pom^.podatak=kljuc) then dete:=pom
     else
      begin
        roditelj:=pom;
        if (pom^.podatak< kljuc) then pom:=pom^.desno
        else pom:=pom^.levo;
      end;
    end;
 end;

if (dete = nil) then roditelj:=nil;

end;

procedure brisi(var koren:pokazivac;kljuc:integer);
var
roditelj,dete,pom,zamena:pokazivac;
begin

//pronalazimo cvor koji sadrzi trazenu vrednost
// dete - cvor koji sadrzi trazenu vrednost 
// roditelj  - roditelj cvora koji sadrzi trazenu vrednost

pronadji(koren,roditelj,dete,kljuc); 

if (dete <> nil) then
  begin
  // ako je cvor koji se brise list
  if ((dete^.levo = nil) and (dete^.desno = nil )) then zamena:=nil 
  // ako cvor koji se brise ima samo levog naslednika
  else if ((dete^.levo <> nil) and (dete^.desno = nil )) then zamena:=dete^.levo
  // ako cvor koji se brise ima samo desnog naslednika
  else if ((dete^.levo = nil) and (dete^.desno <> nil )) then zamena:=dete^.desno
  // ako cvor koji se brise ima oba naslednika
  else
    begin
     pom:=dete^.levo;
     // trazi se krajnji desni potomak levog naslednika
      while(pom^.desno <> nil) do  pom:=pom^.desno;
      pom^.desno := dete^.desno;
      zamena:=dete^.levo;
    end;
    
  // ako cvor nema roditelja, onda je on koren
  if (roditelj = nil) then koren:=zamena
  else
   begin 
     if (roditelj^.levo = dete) then roditelj^.levo := zamena
     else roditelj^.desno:=zamena;
   end;
    
  end;



end;


begin


koren:=nil;
Assign(f,'brisanje.txt');
Reset(f);
Readln(f,br);
while(br <> 0) do
  begin
    dodaj(koren,br);
    Readln(f,br);
  end;
Close(f);  
  lkd(koren);
  
  writeln('Sta brisem ? ');
  Readln(br);
  brisi(koren,br);
  
  writeln('Stablo sada izgleda : koren je ',koren^.podatak);
  lkd(koren);
  end.