Alternate Tree implementation I am trying to implement algorithms related to trees in Scala. I have dabbled with the following implementations of a tree. Are there any pros and cons of preferring the non-Option related implementation over the one that uses Option?

Implementation with Option:

  sealed trait Node {
    val label: Int
  }
  case class LeafNode(override val label: Int) extends Node
  case class BranchNode(override val label: Int, left: Option[Node], right: Option[Node]) extends Node

  def inorderTraversal(aTree: Option[Node]): List[Int] = {
    def helper(aTree: Option[Node], acc: List[Int]): List[Int] = aTree match {
      case None =&gt; acc
      case Some(LeafNode(label)) =&gt; helper(None, label :: acc)
      case Some(BranchNode(label, left, right)) =&gt; helper(left, acc) ++ helper(None, label :: acc) ++ helper(right, acc)
    }
    helper(aTree, List.empty[Int])
  }


Implementation without Option:

  sealed trait Tree {
    def value: Int
    def left: Tree
    def right: Tree
    def isEmpty: Boolean
    def inorder(acc: List[Int]): List[Int] = {
      if (isEmpty) acc else {
        left.inorder(acc) ++ List(value) ++ right.inorder(acc)
      }
    }
  }

  case object Leaf extends Tree {
    override def value = throw new IllegalArgumentException
    override def left = throw new IllegalArgumentException
    override def right = throw new IllegalArgumentException
    override def isEmpty = true
  }

  case class Branch(override val value: Int, left: Tree=Leaf, right: Tree=Leaf) extends Tree {
    override def isEmpty = false
  }


The Option related implementation leads to a lot of pattern matching code, sometimes multiple case statements. Whereas with the non-Option method I can get by using the isEmpty check. I am biased towards the non-Option method because the code appears simpler to follow.

Which one is better and why?
I don't like either implementation, but since you asked, the first one is the least bad since it makes better use of case classes. And that brings me to my first point,

You need to make use of case classes (better)

And it all starts with the first thing you did in your code. Because you did this:

sealed trait Node {
   val label: Int
}


You just automatically eliminated the ability to create empty trees due to the fact that every tree now has to contain an item. This puts you in a bad position because as you have noticed, you now have no choice but to resort to Options. Don't get me wrong, Option monads are great but when used in such a manner it does them no justice.

Anyways, I suggest removing the val label: Int and just having an empty sealed trait.

sealed trait Node {}


Then you can also remove the override from your other classes:

case class LeafNode(label: Int) extends Node
case class BranchNode(label: Int, left: Option[Node], right: Option[Node]) extends Node


Still looks pretty bad, but we can fix that.

Case Objects are still a thing

From the above use of Option, it would seem that you are trying to say that a BranchNode can sometimes contain a node and other times, contain nothing. In that case, let's create a better representation of "Nothing" by making use of case objects:

case object EmptyNode extends Node


Aha! you say

Mhm I reply

Since we now have a case object to represent the Empty state of a tree, let's reconstruct our tree now

case object EmptyNode extends Node
case class LeafNode(label: Int) extends Node
case class BranchNode(label: Int, left: Node, right: Node) extends Node


And there you go, a perfect recipe for great pattern matching.



With this in order, we can now reconstruct the traversal method. Note you have two options with this, either create an implicit class which implements the traversal method and allows you to do tree.inorderTraversal or create a method which takes the tree as you have already done. For this demonstration, I will opt for the implicit class option:

implicit class InorderTraversable(val aTree: Node) extends AnyVal {
    def inorderTraversal: List[Int] = aTree match {
        case EmptyNode =&gt; List()
        case LeafNode(item) =&gt; List(item)
        case BranchNode(item, left, right) =&gt; (left.inorderTraversal :+ item) ++ right.inorderTraversal
    }
}


Other statements


Avoid nesting functions if you can
Try to throw less exceptions
Use pattern matching to your full advantage. Read more here


Putting it all together:

package com.codereview

sealed trait Node {}
case object EmptyNode extends Node
case class LeafNode(label: Int) extends Node
case class BranchNode(label: Int, left: Node, right: Node) extends Node

object Main extends App {
    implicit class InorderTraversable(val aTree: Node) extends AnyVal {
        def inorderTraversal: List[Int] = aTree match {
            case EmptyNode =&gt; List()
            case LeafNode(item) =&gt; List(item)
            case BranchNode(item, left, right) =&gt; (left.inorderTraversal :+ item) ++ right.inorderTraversal
        }
    }

    val tree =
    BranchNode(1,
        BranchNode(2,
            BranchNode(3, 
                BranchNode(4, LeafNode(6), LeafNode(5)),
                BranchNode(7, LeafNode(8), EmptyNode)),LeafNode(9)), LeafNode(10))

    println(tree.inorderTraversal)
}