unit Tree;

interface

uses VCL.GRIDS, System.SysUtils, System.math;

type
   TDIntArr = array of Integer;

   TBTree = class(TObject)
   private
      FVal: Integer;
      FDepth: Integer;
      FLeft, FRight: TBTree;
   public
      constructor Create; overload;
      constructor Create(pVal: Integer); overload;
      destructor Destroy; overload;

      procedure Add(pVal: Integer);
      procedure SetLeft(Left: TBTree);
      procedure SetRight(Right: TBTree);
      function BinarySearch(L, R, pVal: Integer; Arr: TDIntArr;
        var Root: TBTree): Integer;

      property Depth: Integer read FDepth write FDepth;
      property Left: TBTree read FLeft write SetLeft;
      property Right: TBTree read FRight write SetRight;
      property Val: Integer read FVal write FVal;

   end;

implementation

constructor TBTree.Create;
begin
   inherited Create;
   FLeft := nil;
   FRight := nil;
   FDepth := 1;
end;

constructor TBTree.Create(pVal: Integer);
begin
   Create;
   FVal := pVal;
end;

destructor TBTree.Destroy;
begin
   if FLeft <> nil then
      FLeft.Destroy;
   if FRight <> nil then
      FRight.Destroy;
   inherited Destroy;
end;

procedure TBTree.SetLeft(Left: TBTree);
begin
   FLeft := Left;
end;

procedure TBTree.SetRight(Right: TBTree);
begin
   FRight := Right;
end;

procedure TBTree.Add(pVal: Integer);
begin
   if pVal < FVal then
   begin
      if Left = nil then
      begin
         Left := TBTree.Create;
         Left.FVal := pVal;
      end
      else
      begin
         Left.Add(pVal);
      end;
   end
   else
   begin
      if Right = nil then
      begin
         Right := TBTree.Create;
         Right.FVal := pVal;
      end
      else
      begin
         Right.Add(pVal);
      end;
   end;
   if Right <> nil then
      Depth := Max(Depth, 1 + Right.Depth);
   if Left <> nil then
      Depth := Max(Depth, 1 + Left.Depth);
end;

function TBTree.BinarySearch(L, R, pVal: Integer; Arr: TDIntArr;
  var Root: TBTree): Integer;
var
   M, MVal: Integer;
begin
   if L <= R then
   begin
      M := (L + R) div 2;
      MVal := Arr[M];
      Val := MVal;
      if pVal < MVal then
      begin
         Left := TBTree.Create;
         Root.Depth := Root.Depth + 1;
         Result := FLeft.BinarySearch(L, M - 1, pVal, Arr, Root);
      end
      else if pVal = MVal then
      begin
         Result := M;
      end
      else
      begin
         Right := TBTree.Create;
         Root.Depth := Root.Depth + 1;
         Result := FRight.BinarySearch(M + 1, R, pVal, Arr, Root);
      end;
   end
   else
   begin
      Result := -1;
      Val := pVal;
   end;
end;

end.