binarytrees

import os, strutils

type
  TreeNode[T] = object
    item: T
    left, right: TreeNodeRef[T]
  TreeNodeRef[T] = ref TreeNode[T]

proc bottomUpTree(item, depth: int32): TreeNodeRef[int32] =
    new(result)
    if depth > 0:
        var left, right: TreeNodeRef[int32]
        new(left)
        new(right)
        left = bottomUpTree(2*item-1, depth-1)
        right = bottomUpTree(2*item, depth-1)
        result.item = item
        result.left = left
        result.right = right
    else:
        result.item = item

proc itemCheck(noderef: TreeNodeRef[int32]): int32 =
  if noderef.left == nil:
    result = noderef.item
  else:
    result = noderef.item + noderef.left.itemCheck - noderef.right.itemCheck

const minDepth = 4

let args = commandLineParams()

var n: int32 = 0
if args.len > 0:
  n = args[0].parseInt.toU32

let maxDepth: int32 = if minDepth + 2 > n: minDepth + 2
                                     else: n
let stretchDepth: int32 = maxDepth + 1

var check = bottomUpTree(0, stretchDepth).itemCheck
echo "stretch tree of depth ", stretchDepth, "\t check: ", check

let longLivedTree = bottomUpTree(0, maxDepth)

for depth in countup(minDepth, maxDepth, 2):
  let iterations = 1 shl (maxDepth - depth + minDepth)
  check = 0

  for i in countup(1, iterations):
    check += bottomUpTree(i, depth).itemCheck
    check += bottomUpTree(-i, depth).itemCheck

  echo((iterations*2), "\t trees of depth ", depth, "\t check: ", check)

echo "long lived tree of depth ", maxDepth, "\t check: ", longLivedTree.itemCheck