tree1

sealed abstract class Tree[+T]{
    def addValue[ U >: T <% Ordered[U] ](value:U):Tree[U]
    def isMirrowOf[V](tr:Tree[V]):Boolean
    def append[ U >: T <% Ordered[U] ](tr:Tree[U]):Tree[U]
    def isSymmetry:Boolean
    def isEmpty:Boolean
    val height:Int
}
case class Node[+T](val value: T, val left: Tree[T], val right: Tree[T]) extends Tree[T] {
  override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"

  def addValue[ U >: T <% Ordered[U] ](item:U):Tree[U] = {
    if(item>value) Node(value,left,right.addValue(item))
    else if(item<value) Node(value,left.addValue(item),right)
    else this
  }
  /* Return: a new height-balanced tree   */
  def heightBalanced[ U >: T <% Ordered[U] ]:Tree[U] = {
    val lh = left.height
    val rh = right.height
    if( math.abs(lh-rh)<=1 ) this
    else if(rh>lh) left append right addValue value
    else right append left addValue value
  }
  /*
  tree.scala:26: error: No implicit view available from T => Ordered[T].
        else if(rh>lh) left append right addValue value
                                  ^
  tree.scala:27: error: No implicit view available from T => Ordered[T].
          else right append left addValue value
                     ^
  */
  def append[ U >: T <% Ordered[U] ](tr:Tree[U]):Tree[U] = tr match {
    case tr:Node[U] => this addValue tr.value append tr.left append tr.right
    case _ => this
  }

  val height = 1 + ( left.height max right.height )
}
case object End extends Tree[Nothing] {
  override def toString = "."
  def addValue[U <% Ordered[U]](value:U) = Node(value)
  val height = 0
}
object Node {
  def apply[T](value: T): Node[T] = Node(value, End, End)
}