program derevo;

{$APPTYPE CONSOLE}

uses
 SysUtils;

type
 PItem=^TItem;   {перечисление и описание типов }
 TItem=record
 Id:integer;
 Left:Pitem;
 Right:Pitem;
 Parent:Pitem;
 end;

var
root:PItem;       {описание переменных, корень переменная}

 function FindNode(var Root:PItem;Idname:integer):PItem; {функция обхода всех элементов дерева}
var
{s:=integer;}
RetNode:PItem; state:byte;
begin
{s:=0;
s:=s+root.id; }
RetNode:=root;
State:=0;
if Root<>Nil then
 begin
 while true do
   begin
   if Retnode.Id=idname then break;
   if(retnode.Left<>nil)and (State<1)then
     begin
     RetNode:=RetNode.Left;
     {s:=s+retnode.id;}
     State:=0;
     end
     else
     begin
     if (retnode.Right<>nil)and (State<2)then
       begin
       retnode:=retnode.Right;{s:=s+retnode.id;}
       state:=0;
       end
       else
         begin
         if retnode.Parent<>nil then
           begin
           if retnode=retnode.Parent.left then
           state:=1
           else
           state:=2;
           retnode:=retnode.Parent;
           end
           else
             begin
             retnode:=nil;
             break;
             end;
           end;
         end;
       end;
     end;
result:=RetNode;
end;

procedure addnode(var root:PItem;id1,id2:integer);
var
NNode:PItem;
CNode:PItem;
begin Getmem(NNode,sizeof (TItem));
NNode.Id:=id1;
NNode.left:=nil;
NNode.right:=nil;
if root<>nil then
begin
if FindNode(root,id1)<>nil then
writeln ('takoi element uze est')
else
cnode := findnode(root,id2);
if cnode = nil then
writeln(' not find node')
else
if cnode^.left =nil then
begin
cnode.left:= nnode;
nnode.Parent :=cnode
end
else
if cnode^.right =nil then
begin
cnode.right:= nnode;
nnode.Parent :=cnode
end
else
writeln('vse elementi ZANATI NA UZLE');
END
else
begin
root := nnode;
end;
end;

procedure Viv_Tree(root:pitem;level:integer=0);
begin
inc(level);
if root = nil then
begin
writeln('element otsutstvuet');
exit;
end
else begin
write('id  ' + inttostr(root.id));
write('  uroven  ' + inttostr(level));
writeln;
if root.left <> nil then
Viv_Tree(root.left,level);
if root.right <> nil then
Viv_Tree(root.right,level);
end;
end;
function Findmin(var Root:PItem;Idname:integer):PItem; {функция обхода всех элементов дерева}
var
{s:=integer;}
RetNode:PItem; state:byte;
min:integer;
begin
{s:=0;
s:=s+root.id; }
RetNode:=root;
State:=0;
min:=root.id;
if Root<>Nil then
 begin
 while true do
   begin
   if Retnode.Id=idname then break;
   if(retnode.Left<>nil)and (State<1)then
     begin
     RetNode:=RetNode.Left;
     {s:=s+retnode.id;}
     State:=0;
     end
     else
     begin
     if (retnode.Right<>nil)and (State<2)then
       begin
       retnode:=retnode.Right;{s:=s+retnode.id;}
       state:=0;
       end
       else
         begin
         if retnode.Parent<>nil then
           begin
           if retnode=retnode.Parent.left then
           begin
           state:=1;
           if retnode.Id < min then min:=retnode.Id;
           end
           else
           begin
           state:=2;
           if retnode.Id < min then min:=retnode.Id;
           end;

           retnode:=retnode.Parent;
           end
           else
             begin
             retnode:=nil;
             break;
             end;
           end;
         end;
       end;
     end;
result:=RetNode;
writeln('min= ', min);
end;


begin
addnode(root,-1,2);
addnode(root,2,-1);
addnode(root,8,-1);
addnode(root,4,2);
addnode(root,7,2);
addnode(root,9,8);
addnode(root,3,8);
readln;
Viv_Tree(root);
writeln;
Findmin(root,3);
writeln;
readln;
end.