PFDS Exercise 2.5

pfds_exercise_2.5.scala

object BinaryTree {
  def complete[T](x: T, d: Int): BinaryTree[T] = d match {
    case 0 => BinaryTreeLeaf
    case _ => {
      val subtree = complete(x, d - 1)
      BinaryTreeNode(subtree, x, subtree)
    }
  }

  def balanced[T](x: T, d: Int)(implicit ordering: Ordering[T]): BinaryTree[T] = d match {
    case 0 => BinaryTreeLeaf
    case 1 => BinaryTreeNode(BinaryTreeLeaf, x, BinaryTreeLeaf)
    case _ => {
      val half = d / 2
      val halftree = create(x, half)
      if (half * 2 == d) BinaryTreeNode(halftree, x, create(x, half - 1))
      else BinaryTreeNode(halftree, x, halftree)
    }
  }
}