List of tree roots

Time to change gears; we know that binary trees' lookup and update operations are fast. Fast lookup is the result of storing actual data elements in binary trees, that is, all the roots linked up in a list.

Here are our tree definitions:

scala> sealed abstract class Tree { 
     |   def size: Int 
     | } 

Note the use of the sealed keyword. It is sealed, which means the definition could be used in this file only. We have an abstract method to know how many data elements (leaves) exist in this tree:

scala> case class Leaf(n: Int) extends Tree { 
     |   override def size = 1 
     | } 

The Leaf class actually holds the data items. As the name indicates, it is a leaf and there are no children under a leaf:

scala> case object Zero extends Tree { 
     |   override def size = 0 
     | } 

The Zero is a singleton object; it corresponds to the binary 0. We will see it in action pretty soon:

scala> case class One(t: Tree...