routine  BottomUpTree(item:int,  depth:any)  =>  tuple<int,any,any>
{
     if(  depth  >  0  ){
          i  =  item  +  item;
          depth  =  depth  -  1;
          return  (  item,  BottomUpTree(i-1,  depth),  BottomUpTree(i,  depth)  );
     }
     return  (  item,  null,  null  );
}

routine  ItemCheck(  (item:int,  left:any,  right:any)  )  =>int
{
     if(  left  !=  null  )  return  item  +  ItemCheck(left)  -  ItemCheck(right);
     return  item;
}

routine  main(  N  =  10  )
{
     mindepth  =  4;
     maxdepth  =  mindepth  +  2;
     if(  maxdepth  <  N  )  maxdepth  =  N;

     stretchdepth  =  maxdepth  +  1;
     stretchtree  =  BottomUpTree(0,  stretchdepth);

     stdio.printf(  "stretch tree of depth %d\t check: %d\n",  stretchdepth,  ItemCheck(stretchtree)  );

     longlivedtree  =  BottomUpTree(0,  maxdepth);

     for(  depth  =  mindepth  :  2  :  maxdepth  ){
          iterations  =  2  **  (maxdepth  -  depth  +  mindepth);
          check  =  0;
          for(  i  =  1  :  iterations  )
               check  =  check  +  ItemCheck(BottomUpTree(1,  depth))  +  ItemCheck(BottomUpTree(-1,  depth));

          stdio.printf("%d\t trees of depth %d\t check: %d\n",  iterations*2,  depth,  check);
     }
     stdio.printf("long lived tree of depth %d\t check: %d\n",  maxdepth,  ItemCheck(longlivedtree));
#{
#}
}

routine  BottomUpTree(item,  depth)
{
     if(  depth  >  0  ){
          i  =  item  +  item;
          depth  =  depth  -  1;
          left  =  BottomUpTree(i-1,  depth);
          right  =  BottomUpTree(i,  depth);
          return  {  item,  left,  right  };
     }
     return  {  item  };
}

routine  ItemCheck(tree)
{
     #stdio.println( stdlib.about(tree) );
     if(  tree.size()  ==  3  ){
          return  tree[0]  +  ItemCheck(tree[1])  -  ItemCheck(tree[2]);
     }
     return  tree[0];
}

routine  main(  N  =  10  )
{
     mindepth  =  4;
     maxdepth  =  mindepth  +  2;
     if(  maxdepth  <  N  )  maxdepth  =  N;

     stretchdepth  =  maxdepth  +  1;
     stretchtree  =  BottomUpTree(0,  stretchdepth);

     stdio.printf(  "stretch tree of depth %d\t check: %d\n",  stretchdepth,  ItemCheck(stretchtree)  );

     longlivedtree  =  BottomUpTree(0,  maxdepth);

     for(  depth  =  mindepth  :  2  :  maxdepth  ){
          iterations  =  2  **  (maxdepth  -  depth  +  mindepth);
          check  =  0;
          for(  i  =  1  :  iterations  )
               check  =  check  +  ItemCheck(BottomUpTree(1,  depth))  +  ItemCheck(BottomUpTree(-1,  depth));

          stdio.printf("%d\t trees of depth %d\t check: %d\n",  iterations*2,  depth,  check);
     }
     stdio.printf("long lived tree of depth %d\t check: %d\n",  maxdepth,  ItemCheck(longlivedtree));
#{
#}
}

final  class  Node
{
     my  item  =  0;
     my  left  :  Node;
     my  right  :  Node;
}

routine  BottomUpTree(item,  depth)
{
     if(  depth  >  0  ){
          i  =  item  +  item;
          depth  =  depth  -  1;
          left  =  BottomUpTree(i-1,  depth);
          right  =  BottomUpTree(i,  depth);
          return  Node{  item,  left,  right  };
     }
     return  Node{  item  };
}

routine  ItemCheck(tree)
{
     #stdio.println( stdlib.about(tree) );
     if(  tree.left  !=  nil  ){
          return  tree.item  +  ItemCheck(tree.left)  -  ItemCheck(tree.right);
     }
     return  tree.item;
}

routine  main(  N  =  10  )
{
     mindepth  =  4;
     maxdepth  =  mindepth  +  2;
     if(  maxdepth  <  N  )  maxdepth  =  N;

     stretchdepth  =  maxdepth  +  1;
     stretchtree  =  BottomUpTree(0,  stretchdepth);

     stdio.printf(  "stretch tree of depth %d\t check: %d\n",  stretchdepth,  ItemCheck(stretchtree)  );

     longlivedtree  =  BottomUpTree(0,  maxdepth);

     for(  depth  =  mindepth  :  2  :  maxdepth  ){
          iterations  =  2  **  (maxdepth  -  depth  +  mindepth);
          check  =  0;
          for(  i  =  1  :  iterations  )
               check  =  check  +  ItemCheck(BottomUpTree(1,  depth))  +  ItemCheck(BottomUpTree(-1,  depth));

          stdio.printf("%d\t trees of depth %d\t check: %d\n",  iterations*2,  depth,  check);
     }
     stdio.printf("long lived tree of depth %d\t check: %d\n",  maxdepth,  ItemCheck(longlivedtree));
#{
#}
}