4
\$\begingroup\$

I'm working on some Scala problems given here, specifically:

sealed abstract class Tree[+T]
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"
}
case object End extends Tree[Nothing] {
  override def toString = "."
}
object Node {
  def apply[T](value: T): Node[T] = Node(value, End, End)
}

While implementing an insert into a height balanced tree I have the following function:

def insert(node: Tree[Char], value: Char): Tree[Char] = {
    if(node.eq(End)){
      Node(value,End,End)
    }
    else{
      val internalNode = node.asInstanceOf[Node[Char]]
      if(internalNode.left.height == internalNode.right.height){

          if(Random.nextBoolean()){ //choose left
            internalNode.left = insert(internalNode.left,value)
          }else{
            internalNode.right = insert(internalNode.right,value)
          }

      }
      else if(internalNode.left.height > internalNode.right.height){ //insert into right
          internalNode.right = insert(internalNode.right,value)
      }
      else{ //insert into left
          internalNode.left = insert(internalNode.left,value)
      }
      internalNode
    }

  }

Could you please let me know how I could improve this code.

  • Is there a way I can avoid doing the casting in asInstanceOf?

  • How can I improve the if else checks?

General feedback is also much appreciated.

\$\endgroup\$
2
\$\begingroup\$

When you feel yourself going to use a cast, especially when combined with an if on the save variable, then you most likely want to use a match.

def insert(node: Tree[Char], value: Char): Tree[Char] = {
  node match {
    case End => // hand end case here
    case n: Node[Char] => // handle the node case here
    case _ => // throw an exception, or do nothing if this case can't happen
  }
}

Now the node case is complicated enough that you might extract a method for it. Otherwise, it looked fine to me.

\$\endgroup\$
2
\$\begingroup\$

To take full advantage of your generic class, change the insert method definition such that it is also generic:

    def insert[T](node: Tree[T], value: T): Tree[T] = {
        // implementation using pattern matching
    }
\$\endgroup\$
0
\$\begingroup\$
  • As some other post pointed out, it's not clear why you are implementing insert only for Char.

  • I don't like the name End. It's more of an empty slot.

  • You did not show the implementation of height. It's better to post a fully running example. (See my code below.)

  • Your code does not compile. You rightly made the Nodes immutable, but you can't reassign its members:

    internalNode.left = insert(internalNode.left, value)
    

    You can make the members of a case class mutable by declaring them case class Node(var value..., but you should try to stick to immutable data structures.

  • You can also include conditions in the case matching to shorten the code even further.

Here is my implementation with all my suggestions:

  sealed abstract class Tree[+T] {
    def height: Int
  }
  case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
    override def height = 1 + math.max(left.height, right.height)
    override def toString = s"Node(${value}, [left=${left}, right=${right}]"
  }
  case object Empty extends Tree[Nothing] {
    override def height = 1
  }
  object Node {
    def apply[T](value: T): Node[T] = Node(value, Empty, Empty)
  }

  def insert[T](tree: Tree[T], value: T): Tree[T] = {
    val random = new Random(123)
    def insertLeft[T](node: Node[T], value: T) = Node(node.value, insert(node.left, value), node.right)
    def insertRight[T](node: Node[T], value: T) = Node(node.value, node.left, insert(node.right, value))
    tree match {
      case Empty => Node(value)
      case node @ Node(_, l, r) if (l.height > r.height) => insertRight(node, value)
      case node @ Node(_, l, r) if (l.height < r.height) => insertLeft(node, value)
      case node @ Node(_, _, _) => if (random.nextBoolean) insertRight(node, value) else insertLeft(node, value)
    }
  }

I also realized you don't even need algebraic data types: you can use Option instead of an Empty node.

  case class Node[+T](value: T, left: Option[Node[T]] = None, right: Option[Node[T]] = None) {
    def height: Int = 1 + math.max(left.map(n => n.height).getOrElse[Int](0), right.map(n => n.height).getOrElse[Int](0))
    override def toString = s"Node(${value}, [left=${left}, right=${right}]"
  }

  def insert[T](tree: Node[T], value: T): Node[T] = {
    val random = new Random(123)
    tree match {
      case Node(v, None, None) => if (random.nextBoolean) Node(v, Some(Node(value)), None) else Node(v, None, Some(Node(value)))
      case Node(v, None, Some(r)) => Node(v, Some(Node(value)), Some(r))
      case Node(v, Some(l), None) => Node(v, Some(l), Some(Node(value)))
      case Node(v, Some(l), Some(r)) => if (random.nextBoolean) Node(v, Some(insert(l, value)), Some(r)) else Node(v, Some(l), Some(insert(r, value)))
    }
  }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.