# binary-trees Ada 2012 GNAT program

## source code

```-- The Computer Language Benchmarks Game
-- https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
--
-- Contributed by Jim Rogers
-- *reset*

with Treenodes; use Treenodes;

procedure Binarytrees is
Min_Depth : constant Positive := 4;
N : Natural := 1;
Stretch_Tree : TreeNode;
Long_Lived_Tree : TreeNode;
Short_Lived_Tree_1 : TreeNode;
Short_Lived_Tree_2 : TreeNode;
Max_Depth : Positive;
Stretch_Depth : Positive;
Check : Integer;
Sum : Integer;
Depth : Natural;
Iterations : Positive;
begin
if Argument_Count > 0 then
N := Positive'Value(Argument(1));
end if;
Max_Depth := Positive'Max(Min_Depth + 2, N);
Stretch_Depth := Max_Depth + 1;
Stretch_Tree := Bottom_Up_Tree(Stretch_Depth);
Item_Check(Stretch_Tree, Check);
Put("stretch tree of depth ");
Put(Item => Stretch_Depth, Width => 1);
Put(Ht & " check: ");
Put(Item => Check, Width => 1);
New_Line;

Long_Lived_Tree := Bottom_Up_Tree(Max_Depth);

Depth := Min_Depth;
while Depth <= Max_Depth loop
Iterations := 2**(Max_Depth - Depth + Min_Depth);
Check := 0;
for I in 1..Iterations loop
Short_Lived_Tree_1 := Bottom_Up_Tree(Depth => Depth);
Item_Check(Short_Lived_Tree_1, Sum);
Check := check + Sum;
end loop;
Put(Item => Iterations, Width => 0);
Put(Ht & " trees of depth ");
Put(Item => Depth, Width => 0);
Put(Ht & " check: ");
Put(Item => Check, Width => 0);
New_Line;
Depth := Depth + 2;
end loop;
Put("long lived tree of depth ");
Put(Item => Max_Depth, Width => 0);
Put(Ht & " check: ");
Item_Check(Long_Lived_Tree, Check);
Put(Item => Check, Width => 0);
New_Line;
end BinaryTrees;
----------------------------------------------------------------
-- BinaryTrees
--
--
-- Contributed by Jim Rogers
----------------------------------------------------------------

package Treenodes is
type Treenode is private;
function Bottom_Up_Tree(Depth : Integer) return Treenode;
procedure Item_Check(This : in out Treenode; Sum : out Integer);
private
type Node;
type Treenode is access Node;
type Node is record
Left  : Treenode := null;
Right : Treenode := null;
end record;
end Treenodes;
----------------------------------------------------------------
-- BinaryTrees
--
--
-- Contributed by Jim Rogers
----------------------------------------------------------------

package body Treenodes is
function Bottom_Up_Tree(Depth : Integer)
return Treenode is
begin
if Depth > 0 then
return new Node'(Bottom_Up_Tree(Depth -1),
Bottom_Up_Tree(Depth -1));
else
return new Node'(null, null);
end if;
end Bottom_Up_Tree;

procedure Item_Check (This : in out Treenode; Sum : out Integer) is
procedure Free is new Ada.Unchecked_Deallocation(Node, Treenode);
Left_Sum, Right_Sum : Integer;
begin
if This.Left = null then
Sum := 1;
else
Item_Check(This.Left, Left_Sum);
Item_Check(This.Right, Right_Sum);
Sum :=  1 + Left_Sum + Right_Sum;
end if;
Free(This);
end Item_Check;

end Treenodes;
```

## notes, command-line, and program output

```NOTES:
GNATMAKE 13.2.0

Wed, 22 May 2024 02:38:12 GMT

MAKE:
gnatchop -r -w binarytrees.gnat
splitting binarytrees.gnat into:
gnatmake -O3 -fomit-frame-pointer -march=ivybridge -gnatNp -f binarytrees.adb -o binarytrees.gnat_run -largs -lapr-1
x86_64-linux-gnu-gcc-13 -c -O3 -fomit-frame-pointer -march=ivybridge -gnatNp binarytrees.adb
x86_64-linux-gnu-gcc-13 -c -O3 -fomit-frame-pointer -march=ivybridge -gnatNp treenodes.adb
x86_64-linux-gnu-gnatbind-13 -x binarytrees.ali
x86_64-linux-gnu-gnatlink-13 binarytrees.ali -O3 -fomit-frame-pointer -march=ivybridge -o binarytrees.gnat_run -lapr-1

3.84s to complete and log all make actions

COMMAND LINE:
./binarytrees.gnat_run 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303
```