Scala: Create a binary Tree from List

Question

I'm a complete beginner in Scala. So my question might be quite stupid, please be patient with me. I have a template for a binary tree structure:

sealed trait Tree[T]
case class Leaf[T]() extends Tree[T]
case class Node[T](left: Tree[T], data :Int, right Tree[T]) extends Tree[T]

I want to write a function which creates a binary tree from a list. The first list element is the root. All data left of a branch are smaller and all data right of a branch are bigger:

def listToTree[T](list: List[T]): Tree[T]

I'm not sure what I wrote wrong, but my output is always only the first List element

def setElement(x: Int, tree: Tree[Int]): Tree[Int] = tree match {
    case Node(l, e, r) => Node(l, x, r)
    case Leaf() => new Node(Leaf(), x, Leaf()) 
}
def listToTree2[T](as: List[Int], tree: Tree[Int], x: Int): Tree[Int] = tree match
{
  case Leaf() => listToTree2(as.tail, setElement(as.head, tree), x)
  case Node(left, e, right) => if(e < x) {
    right match {
      case Leaf() => listToTree2(as.tail, setElement(as.head, tree), x)
      case Node(left2, e2, right2) => if( e < e2) listToTree2(as, right, x)
      else listToTree2(as, left, x)
    }
  } else if(e > x) { 
    left match {
      case Leaf() => listToTree2(as.tail, setElement(as.head, tree), x)
      case Node(left3, e3, right3) => if( e < e3) listToTree2(as, right, x) else listToTree2(as, left, x)
    }
  } else {
    listToTree2(as.tail, tree, x)
  }
}


def listToTree[T](as: List[Int]): Tree[Int] =
{
  val tree = new Node(Leaf(), as.head, Leaf())
  listToTree2(as, tree, as.head)
}

So in the end the correct output should be something like this:


val list = List(3, 2, 4, 1)
assert(listToTree(list) == Branch(Branch(Branch(Leaf(),1,Leaf()),2,Leaf()))),3,Branch(Leaf(),4,Leaf()))

Dima · Accepted Answer · 2021-05-04 21:05:16Z

3

There are a few things in your code that don't seem to make a lot of sense ... But more importantly, what you have written looks linear to me, and I am pretty sure you can't build a BST in linear time (if you could, you could also sort in linear time then, which would be pretty cool). So, it looks like rather than trying to debug this code, you are better off throwing it out, and rethinking your entire approach.

Immutable structures don't make it particularly easy to implement non-linear things, unfortunately. There are several approaches you could try here. One in particular is borrowing the partition idea from the quick sort:

def makeTree(data: List[Int]): Tree[Int] = data match {
   case Nil => Leaf()
   case head :: tail => 
      val (left, right) = tail.partition(_ < head)
      Branch(makeTree(left), head, makeTree(right.filterNot(_ == head)))
}

edited May 4, 2021 at 21:05

answered May 4, 2021 at 16:44

Dima

40.6k6 gold badges54 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Luis Miguel Mejía Suárez · Accepted Answer · 2021-05-04 17:34:44Z

This seems to work:

sealed trait Tree[+T] extends Product with Serializable
final case class Branch[+T](left: Tree[T], elem: T, right: Tree[T]) extends Tree[T]
final case object Leaf extends Tree[Nothing]

object Tree {
  def addToTree[T : Ordering](tree: Tree[T])(t: T): Tree[T] = {
    import Ordering.Implicits._
    
    tree match {
      case Leaf =>
        Branch(left = Leaf, elem = t, right = Leaf)

      case branch @ Branch(left, elem, right) =>
        if (t <= elem) branch.copy(left = addToTree(tree = left)(t))
        else branch.copy(right = addToTree(tree = right)(t))
    }
  }

  def fromList[T : Ordering](data: List[T]): Tree[T] = {    
    data match {
      case root :: tail =>
        tail.foldLeft(Branch(left = Leaf, elem = root, right = Leaf) : Tree[T]) {
          case (acc, t) =>
            addToTree(acc)(t)
        }
      
      case Nil =>
        Leaf
    }
  }
}

Note that I divided the problem into multiple steps, first creating a Tree from a List is basically just starting with a Branch that has the root and then start adding each element in the List to that base Tree.
And adding an element to a Tree can also be decomposed into adding it to the left or to the right accordingly.

You can see the code running in Scastie.

Collectives™ on Stack Overflow

Scala: Create a binary Tree from List

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related