program tree (input,output);
const  nul =0;
       n=20;
        n1=10;

var top,q,parent,value,node,root,p:integer;
        full,found,fulltree,empty,quit,emptytree,insert : boolean;
        stack :array [1..n] of integer;
        lp,rp,data : array [1..n1] of integer;


procedure initstack;
  begin
        begin
                full:=false;
                empty:=true;
                top:=n;
        end;
end;


procedure push(p:integer);
        begin
                empty:=false;
                if not full then
                        begin
                                stack[top]:=p;
                                top:=top-1;
                                if top=0 then full:=true;
                        end
                else
                        begin
                                writeln ('stack overflow !!!');
                                quit:=true;
                        end;
        end;


function pop:integer;
begin
        full:=false;
        if not empty then
                begin
                        top:=top+1;
                        pop:=stack[top];
                        if top=n then empty:=true
                        else;
                end
        else;
end;


procedure moveleft;
  begin
        if not full then
                        repeat
                                begin
                                        push(p);
                                        p:=lp[p];
                                end
                        until (p=nul) or full
        else
                 writeln ('overflow stack');
end;


procedure moveright;
  begin
        repeat
                begin
                        p:=pop;
                        writeln (data[p]);
                end
        until (rp[p]<>nul) or empty;
        if (rp[p]=nul) and empty then quit:=true else
                begin
                        p:=rp[p];
                        moveleft;
                end;
end;

procedure scan;
  begin
if not emptytree then begin
quit:=false;
  p:=root;
        moveleft;
        while not quit do moveright;
  end
else writeln ('tree empty');
  end;

procedure initree;
  begin
        emptytree:=true;
        root:=nul;
        fulltree:=false;
        for p:=1 to n1 do
                begin
                        lp[p]:=nul;
                        rp[p]:=nul;
                end;
  end;


procedure addnode(q:integer);
  begin
  if emptytree then
   begin
     root:=q;
     emptytree:=false;
   end
  else
  begin
    p:=root;
    insert:=false;
    while not insert do
        begin
                if data[q]<=data[p] then
                        begin
                                 if lp[p]=nul then
                                         begin
                                                 insert:=true;
                                                 lp[p]:=q;
                                         end
                                 else p:=lp[p];
                        end
                else
                        begin
                                 if rp[p]=nul then
                                         begin
                                                 insert:=true;
                                                 rp[p]:=q;
                                         end
                                 else p:=rp[p];
                        end;
        end;
end;
end;


procedure search;
  begin
        node:=0;
        found:=false;
        parent:=0;
        p:=root;
        while not found do
          begin
                if value=data[p] then
                  begin
                        found:=true;
                        node:=p;
                  end
                else
                  begin
                        if value < data[p] then
                          if lp[p]<>nul then
                                begin
                                  parent:=p;
                                  p:=lp[p];
                                end
                          else
                                begin
                                  node:=0;
                                  parent:=0;
                                  found:=true;
                                  writeln ('value not in tree');
                                end
                        else
                          if rp[p]<>nul then

                          begin
                                parent:=p;
                                p:=rp[p];
                          end
                        else
                          begin
                                node:=0;
                                parent:=0;
                                found:=true;
                                writeln (' value not in tree');
                          end;
                  end;
                end;
        end;
procedure delete;
begin
if node=root then begin
     if (lp[node]=nul) and (rp[node]=nul) then initree else;
     if (lp[node]=nul) and (rp[node]<>nul) then root:=rp[node] else;
     if (lp[node]<>nul) and (rp[node]=nul) then root:=lp[node] else;
     if (lp[node]<> nul) and (rp[node]<> nul) then
        begin
          root:=lp[node];
          p:=lp[node];
          while rp[p]<>nul do p:=rp[p];
         rp[p]:=rp[node];
        end
     else;
  end
else
  begin
        if lp[node]=0 then
          if rp[parent]=node then
                rp[parent]:=rp[node]
          else lp[parent]:=rp[node]
        else
          if rp[node]=0 then
                if rp[parent]=node then rp[parent]:=lp[node]
                else lp[parent]:=lp[node]
          else
                if lp[parent]=node then
                  begin
                        lp[parent]:=lp[node];
                        p:=lp[node];
                        while rp[p]<>nul do p:=rp[p];
                         rp[p]:=rp[node];
                  end
                else
                  begin
                        rp[parent]:=lp[node];
                        p:=lp[node];
                        while rp[p]<>nul do p:=rp[p];
                        rp[p]:=rp[node];
                  end
  end;
end;

begin (*main program*);
  initree;
  initstack;
    for q:=1 to n1 do
        begin
                writeln ('give node to add');
                readln (data[q]);
                addnode(q);
                scan;
        end;

(*deletion section*)
while not emptytree do
        begin
                writeln ('give node to delete');
                readln (value);
                search;
                if node<>0 then delete else writeln ('value not found');
                scan;
        end;
end.