program PerfectBalancedTree;

type
  pSTreeNode = ^TSTreeNode;
  TSTreeNode = record
    info : integer;
    key : integer;
    left : pSTreeNode;
    right : pSTreeNode;
  end;

var
  pRoot, pPerm : pSTreeNode;
  answer, key : integer;

function searchTheNode(key : integer) : pSTreeNode;
var
  pTemp : pSTreeNode;
begin
  pTemp := pRoot;
  if (pTemp^.key = key) then
  begin
    searchTheNode := pPerm;
  end else
  if (pTemp^.key > key) then
  begin
    if (pTemp^.left <> nil) then
    begin
      pTemp := pTemp^.left;
      searchTheNode(key);
    end else
    begin
      searchTheNode := pPerm;
    end;
  end else
  if (pTemp^.key < key) then
  begin
    if (pTemp^.right <> nil) then
    begin
      pTemp := pTemp^.right;
      searchTheNode(key);
    end else
    begin
      searchTheNode := pPerm;
    end;
  end;
end;

procedure addTheNode(key : integer);
var
  pTemp, pNew : pSTreeNode;
begin
  new(pNew);
  pNew^.info := key;
  pNew^.key := key;
  pNew^.left := nil;
  pNew^.right := nil;
  if (pRoot = nil) then
  begin
    pRoot := pNew;
  end else
  begin
    pTemp := searchTheNode(key);
    if (pTemp^.key > key) then
    begin
      pTemp^.left := pNew;
    end else
    if (pTemp^.key < key) then
    begin
      pTemp^.right := pNew;
    end;
  end;
end;

begin
  pRoot := nil;
  repeat
    writeln('1. add');
    writeln('2. search');
    readln(answer);
    if answer = 1 then
    begin
      write('key: ');
      readln(key);
      addTheNode(key);
    end;
  until answer = 3;
end.