# binary-trees Chapel #3 program

## source code

```/* The Computer Language Benchmarks Game
https://salsa.debian.org/benchmarksgame-team/benchmarksgame/

contributed by Casey Battaglino, Ben Harshbarger, and Brad Chamberlain
derived from the GNU C version by Jeremy Zerfas
*/

use DynamicIters;

config const n = 10;         // the maximum tree depth

proc main() {
const minDepth = 4,                      // the shallowest tree
maxDepth = max(minDepth + 2, n),   // the deepest normal tree
strDepth = maxDepth + 1,           // the depth of the "stretch" tree
depths = minDepth..maxDepth by 2;  // the range of depths to create
var stats: [depths] (int,int);           // stores statistics for the trees

//
// Create the short-lived "stretch" tree, checksum it, and print its stats.
//
{
const strTree = new Tree(strDepth);
writeln("stretch tree of depth ", strDepth, "\t check: ", strTree.sum());
}

//
// Build the long-lived tree.
//
const llTree = new Tree(maxDepth);

//
// Iterate over the depths in parallel, dynamically assigning them
// to tasks.  At each depth, create the required trees, compute
// their sums, and free them.
//
forall depth in dynamic(depths) {
const iterations = 2**(maxDepth - depth + minDepth);
var sum = 0;

for i in 1..iterations {
const t = new Tree(depth);
sum += t.sum();
}
stats[depth] = (iterations, sum);
}

//
// Print out the stats for the trees of varying depths.
//
for (depth, (numTrees, checksum)) in zip(depths, stats) do
writeln(numTrees, "\t trees of depth ", depth, "\t check: ", checksum);

//
// Checksum the long-lived tree, print its stats, and free it.
//
writeln("long lived tree of depth ", maxDepth, "\t check: ", llTree.sum());
}

//
// A simple balanced tree node class
//
class Tree {
var left, right: unmanaged Tree?;

//
// A Tree-building initializer
//
proc init(depth) {
if depth > 0 {
left  = new unmanaged Tree(depth-1);
right = new unmanaged Tree(depth-1);
}
}

//
// Add up tree node, freeing as we go
//
proc sum(): int {
var sum = 1;
if left {
sum += left!.sum() + right!.sum();
delete left, right;
}
return sum;
}
}
```

## notes, command-line, and program output

```NOTES:
chpl version 1.29.0
built with LLVM version 14.0.0
Hewlett Packard
Enterprise Development LP

Wed, 25 Jan 2023 21:11:17 GMT

MAKE:
mv binarytrees.chapel-3.chapel binarytrees.chapel-3.chpl
/opt/src/chapel-1.29.0/bin/chpl --fast binarytrees.chapel-3.chpl -o binarytrees.chapel-3.chapel_run
rm binarytrees.chapel-3.chpl

18.45s to complete and log all make actions

COMMAND LINE:
./binarytrees.chapel-3.chapel_run --n=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
```