Alternate Tree implementation
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)
}