Node definitions
Similar to lists, our binary tree is a trait, BinTree[+A]:
sealed trait BinTree[+A] case object Leaf extends BinTree[Nothing] case class Branch[A](value: A, left: BinTree[A], right: BinTree[A]) extends BinTree[A]
The sealed trait BinTree[+A] array defines a sealed trait. As it is sealed, we can extend it only in the same source file. We saw in Chapter 3, Lists how this helps the compiler to check for exhaustive pattern matching:
case object Leaf extends BinTree[Nothing]
The Leaf node is a terminator node, just like we have the Nil node in lists. Just like Nil, Leaf is a case object, as we just need only one instance of it:
case class Branch[A](value: A, left: BinTree[A], right: BinTree[A]) extends BinTree[A]
The Branch node holds a value, of type A, and a left and right subtree. These subtrees could be either branches or leaves.
Thus, we define the binary tree in terms of itself; in other words, it is a recursively defined structure, similar to List:
Note
Note that this...
