// P63 (**) Construct a complete binary tree.
//     A complete binary tree with height H is defined as follows: The levels
//     1,2,3,...,H-1 contain the maximum number of nodes (i.e 2^(i-1) at the
//     level i, note that we start counting the levels from 1 at the root).  In
//     level H, which may contain less than the maximum possible number of
//     nodes, all the nodes are "left-adjusted".  This means that in a
//     levelorder tree traversal all internal nodes come first, the leaves come
//     second, and empty successors (the Ends which are not really nodes!) come
//     last.
//    
//     Particularly, complete binary trees are used as data structures (or
//     addressing schemes) for heaps.
//    
//     We can assign an address number to each node in a complete binary tree by
//     enumerating the nodes in levelorder, starting at the root with number 1.
//     In doing so, we realize that for every node X with address A the
//     following property holds: The address of X's left and right successors
//     are 2*A and 2*A+1, respectively, supposed the successors do exist.  This
//     fact can be used to elegantly construct a complete binary tree structure.
//     Write a method completeBinaryTree that takes as parameters the number of
//     nodes and the value to put in each node.
//
//     scala> Tree.completeBinaryTree(6, "x")
//     res0: Node[String] = T(x T(x T(x . .) T(x . .)) T(x T(x . .) .))

object Tree {
  def completeBinaryTree[T](nodes: Int, value: T): Tree[T] = {
    def generateTree(addr: Int): Tree[T] =
      if (addr > nodes) End
      else Node(value, generateTree(2 * addr), generateTree(2 * addr + 1))
    generateTree(1)
  }
}