Binary Search Tree in Scala

In this post we are going to make a structure which is similar to Binary Search Tree (BST).

Each node contains an integer element and two child nodes. All the nodes having value less than the current node will be on the left and all nodes having value greater will be on right. If a node doesn't have any child then it will have empty node at that place.

From the description, we can deduce that there are two types on integer nodes - Empty and Non Empty. The operations can be to add a new node or to check if a node exists in the current tree. Hence lets define an abstract class IntNode with these two abstract functions.

IntNode.scala

abstract class IntNode {
  def incl(x: Int): IntNode
  def contains(x: Int): Boolean
}

This abstract class will have its first concrete implementation as Empty node. This is empty node, hence its contains function will always return false. The incl function will take an integer value and create a non-empty node. The code is as follows.

Empty.scala

class Empty extends IntNode {
  def incl(x: Int): IntNode = new NonEmpty(x, new Empty, new Empty)
  def contains(x: Int): Boolean = false
  override def toString = " . "
}

Another concrete implementation of IntNode is NonEmpty node which is as follows.

NonEmpty.scala

class NonEmpty(elem: Int, left: IntNode, right: IntNode) extends IntNode {

  def incl(x: Int): IntNode =
    if (x < elem)
      new NonEmpty(elem, left incl x, right)
    else if (x > elem)
      new NonEmpty(elem, left, right incl x)
    else
      this

  def contains(x: Int): Boolean =
    if (x < elem)
      left contains x
    else if (x > elem)
      right contains x
    else
      true

  override def toString = " { " + left + elem + right + " } "
}

The toString function is overridden to print Empty node as dot(.) and non-empty node in the order of left, element and then right node(s).

Let's first take the contains function. It compares the element x passed to it with current node element and takes a decision based on the BST property. If an element doesn't exists in the tree then it recursively reaches the Empty node of which the contains function returns false.

The incl function also uses the property of BST to add a new node. If the element already present in the list, then it avoids duplication by returning this reference. Otherwise it accordingly reconstruct the tree.

The sample Main class and its output are as follows.

Main.scala

object Main extends App {

  val t1 = new Empty
  println("t1 = " + t1)

  val t2 = t1 incl 4
  println("t2 = " + t2)

  val t3 = t2 incl 1
  println("t3 = " + t3)

  val t4 = t3 incl 5
  println("t4 = " + t4)

  val t5 = t4 incl 2 incl 7 incl 0
  println("t5 = " + t5)

  println("t1 contains 4 = " + (t1 contains 4))
  println("t2 contains 4 = " + (t2 contains 4))
  println("t5 contains 4 = " + (t5 contains 4))
  println("t5 contains 0 = " + (t5 contains 0))
  println("t5 contains 9 = " + (t5 contains 9))

  val t6 = t5 incl 1
  println("t6 = " + t6)

}

Output

t1 =  . 
t2 =  {  . 4 .  } 
t3 =  {  {  . 1 .  } 4 .  } 
t4 =  {  {  . 1 .  } 4 {  . 5 .  }  } 
t5 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  } 
t1 contains 4 = false
t2 contains 4 = true
t5 contains 4 = true
t5 contains 0 = true
t5 contains 9 = false
t6 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  }