tree1-2.scala

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:25: error: type mismatch;
 found   : Node[T(in class Node)]
 required: Tree[T(in method heightBalanced)]
        if( math.abs(lh-rh)<=1 ) this
                                 ^
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
                   ^
                   
*/

/*

  My question:
    1. In method " heightBalanced " , we do not do any comparison between values of T , why do we still need Ordered[U]?
    2. In the type mismatch error, isn't Node[T] a subtype of Tree[T] since Tree is covariant?
*/

tree1.scala

sealed abstract class Tree[+T]{
	def addValue[ U >: T <% Ordered[U] ](value:U):Tree[U]
	def append[ U >: T <% Ordered[U] ](tr:Tree[U]):Tree[U] 
	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)
}