#pragma indent
using System

[Record] \
class TreeNode 
   left : TreeNode
   right : TreeNode
   item : int

   this (i : int)
     item = i

   internal static bottomUp (item : int,  depth : int) : TreeNode
     if (depth > 0)
       TreeNode (bottomUp (2 * item - 1, depth - 1),
                 bottomUp (2 * item, depth - 1), item)
     else
       TreeNode (item)

   internal itemCheck () : int
      // if necessary deallocate here 
      if (left == null) item
      else item + left.itemCheck () - right.itemCheck ()


def minDepth = 4

def args = Environment.GetCommandLineArgs ()
def n = if (args.Length < 2) 0 else int.Parse (args [1])
def maxDepth = Math.Max (minDepth + 2, n)
def stretchDepth = maxDepth + 1

mutable check = TreeNode.bottomUp (0, stretchDepth).itemCheck ()
Console.WriteLine ($ "stretch tree of depth $stretchDepth\t check: $check")

def longLivedTree = TreeNode.bottomUp (0, maxDepth);

for (mutable depth = minDepth; depth <= maxDepth; depth += 2)
  def iterations = 1 << (maxDepth - depth + minDepth)

  check = 0;
  for (mutable i = 1; i <= iterations; i++)
    check += (TreeNode.bottomUp(i,depth)).itemCheck()  
    check += (TreeNode.bottomUp(-i,depth)).itemCheck()

  Console.WriteLine ($ "$(iterations * 2)\t trees of depth $depth\t "
                       "check: $check")

Console.WriteLine ($ "long lived tree of depth $maxDepth\t "
                     "check: $(longLivedTree.itemCheck ())")