import std.math.*
import std.time.*

class TreeNode {
  let left: Option<TreeNode>
  let right: Option<TreeNode>

  init() {
    this.left = None
	  this.right = None
  }

  init(left: TreeNode, right: TreeNode) {
    this.left = Some(left)
	  this.right = Some(right)
  }

  static func bottomUpTree(depth: Int32): TreeNode {
    if (depth > 0) {
	  return TreeNode(bottomUpTree(depth-1), bottomUpTree(depth-1))
	  }
	  else {
	    return TreeNode()
	  }
  }

  func itemCheck(): Int32 {
    match (this.left) {
	    case $None => 1
	    case Some(lt) => match (this.right) {
	    case $None => throw NoneValueException()
		  case Some(rt) => return 1 + lt.itemCheck() + rt.itemCheck()
		  }
	  }
  }
}

func main() {
  var start = DateTime.now()

  let n: Int32 = 21
  let minDepth: Int32 = 4

  var maxDepth: Int32
  if (minDepth + 2 > n) {
    maxDepth = minDepth + 2
  }
  else {
     maxDepth = n
  }
  let stretchDepth: Int32 = maxDepth + 1

  var check: Int32 = (TreeNode.bottomUpTree(stretchDepth)).itemCheck()
  print("stretch tree of depth ${stretchDepth}\t check: ${check}\n")

  var longLivedTree = TreeNode.bottomUpTree(maxDepth)

  var depth: Int32 = minDepth
  while (depth <= maxDepth) {
    var iterations = 1 << (maxDepth - depth +minDepth)
    check = 0
    for (i in 1..iterations+1) {
      check = check + (TreeNode.bottomUpTree(depth)).itemCheck()
    }
    print("${iterations} \t trees of depth ${depth} \t check: ${ check }\n")
    depth = depth + 2
  }
  print("long lived tree of depth ${maxDepth}\t check: ${ longLivedTree.itemCheck() }\n")

  var end = DateTime.now()
  print("time = ${ end - start }\n")
}