binary-trees C clang #8 program

/* The Computer Language Benchmarks Game
   https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
 
   contributed by Isaac Gouy
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct t {
   struct t* left;
   struct t* right;
} Tree;

Tree* new_tree(Tree* left, Tree* right) {
   Tree* new = (Tree*)malloc(sizeof(Tree));
   new->left = left;
   new->right = right;
   return new;
} 

Tree* tree_with(int depth) {
   return (depth == 0) 
      ? new_tree(NULL, NULL)
      : new_tree( tree_with(depth-1), tree_with(depth-1));
}

long node_count(Tree* t) {
   if (t->left == NULL)
      return 1;
   else
      return 1 + node_count(t->left) + node_count(t->right);
}

void clear(Tree* t) {
   if (t->left != NULL) {
      clear(t->left);   
      free(t->left);      
      clear(t->right); 
      free(t->right);       
   }
}

int count(int depth) {
   Tree *t = tree_with(depth);
   int c = node_count(t);  
   clear(t);
   return c;
}

void stretch(int depth) {  
   printf ("stretch tree of depth %i\t check: %i\n", depth, count(depth));   
}

int main(int argc, char *argv[]) {
   int n = 10;
   if (argv[1] > 0) n = atoi(argv[1]);

   int min_depth = 4;
   int max_depth = (min_depth + 2 > n) ? min_depth + 2 : n;
   int stretch_depth = max_depth + 1;

   stretch(stretch_depth);   
   Tree *long_lived_tree = tree_with(max_depth);

   for (int depth = min_depth; depth <= max_depth; depth += 2) {
      int iterations = 1 << (max_depth - depth + min_depth);      
      int sum = 0;
      for (int i = 1; i <= iterations; i++) {
         sum += count(depth);
      }         
      printf ("%i\t trees of depth %i\t check: %i\n", 
         iterations, depth, sum);                 
   }
   int c = node_count(long_lived_tree);
   clear(long_lived_tree);   
   printf ("long lived tree of depth %i\t check: %i\n", 
      max_depth, c); 
   
   return 0;
}
    

NOTES:
64-bit Ubuntu quad core
Ubuntu clang version 18.1.8 (11)


 Wed, 23 Oct 2024 01:06:34 GMT

MAKE:
/usr/bin/clang -pipe -Wall -O3 -fomit-frame-pointer -march=ivybridge  binarytrees.clang-8.c -o binarytrees.clang-8.clang_run 
rm binarytrees.clang-8.c

6.03s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.clang-8.clang_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