CODEWITHSUNDEEP
scalalisttreebinary-tree
user2316721
user2316721

Reputation: 19

Binary tree in Scala

I'm trying to write a function that will be transforming list of integers of binary tree. This is my code:

sealed trait btree[+A]
case class Empty extends btree[Nothing]
case class Node[+A](elem: A, left : btree[A], right : btree[A]) extends btree[A]

def list2btree(list : List[Int]) : btree[Int] = {
def insert2tree(x : Int, t : btree[Int]) : btree[Int] = {
    (x, t) match {
        case (x, Empty) => Node(x, Empty, Empty)
        case (x, Node(v, left, right)) => {
            if(v > x) Node(v, insert2tree(x, left), right)
            else if(v < x) Node(v, left, insert2tree(x,right))
            else throw new Exception("Element exsist!")
        }
    }
}

list match {
    case Nil => Empty
    case (h::t) => insert2tree(h, list2btree(t))
}
}

But it doesn't work. Can you help me with this?

Upvotes: 1

Views: 4087

Answers (1)

Marth
Marth

Reputation: 24802

Empty doesn't need to be a class, it should just be an object : 

sealed trait btree[+A]
case object Empty extends btree[Nothing]
case class Node[+A](elem: A, left : btree[A], right : btree[A]) extends btree[A]

Then your code works (although you are adding elements in a reverse order, which may not be what you want):

scala> list2btree(List(6,2,3,1,4))
res0: btree[Int] = Node(4,Node(1,Empty,Node(3,Node(2,Empty,Empty),Empty)),Node(6,Empty,Empty))

Edit : On the error itself, if Empty is a case class, you need to had () after to specify you want an instance of the Empty class : 

scala> case class Empty
<console>:1: warning: case classes without a parameter list have been deprecated;
use either case objects or case classes with `()' as parameter list.

scala> Empty
res0: Empty.type = Empty

scala> Empty()
res1: Empty = Empty()

Upvotes: 2

Related Questions