Binary Tree using Scala

Question

class MyBst {
  def createTree(list:List[Int]): Node={
    require(list.nonEmpty)
      val nodes = list.map(element => Node(None, element, None))
      val root = nodes.head
      def create(node:List[Node], tree:Node):Node=
        nodes match{
          case head::tail => create(tail,insert(tree,head))
          case Nil => tree
        }
      create(nodes.tail,root)
  }
  def insert(tree:Node,elem:Node):Node = {
    if(tree.data >= elem.data)
      if(tree.left.isDefined)
        tree.copy(left = Some(insert(tree.left.get,elem)))
       else
        tree.copy(left = Some(elem))
    else
      if(tree.right.isDefined)
        tree.copy(right = Some(insert(tree.right.get,elem)))
      else
        tree.copy(right=Some(elem))
  }

}
case class Node(left:Option[Node], data:Int, right:Option[Node])

I m trying to create a tree using scala. But this is not working. It is showing Stack Over Flow Error.

[info] java.lang.StackOverflowError:

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

[info] at binarySearchTree.MyBst.insert(MyBst.scala:21)

Hint : A stack overflow indicates the call stack has grown too big and exceeded available memory. This is most probably due to a mistake in your recursion. — Oliver Shaw
– Oliver Shaw, Commented Jan 30, 2016 at 7:49

stew · Accepted Answer · 2016-01-30 08:05:26Z

1

in your create function, you are pattern matching on nodes instead of node. As soon as you fix that, you are probably going to realize that create Tree doesn't return the top of the tree

edited Jan 30, 2016 at 8:05

answered Jan 30, 2016 at 7:52

stew

11.4k39 silver badges49 bronze badges

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

Collectives™ on Stack Overflow

Binary Tree using Scala

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related