Making a very basic binary tree in Scala

Question

I am trying to make a very simple binary tree in Scala for data storage and traversal.

Right now I have:

trait Tree
case class Node(left: Tree, value: String, right: Tree) extends Tree

My questions:

1. How can I also include a pointer to a parent?

2. Can I have left and right point to null in any way? Or the parent pointer for the root node?

3. How can I actually traverse the tree?

4. Is it easy to update the values of a node?

Answer 1

1. Not with immutable case classes. It is a circular dependency: you need the parent to create the children, but you also need the children to create the parent. On the other hand most tree traversal algorithms don't really need the parent as the parent is usually on the stack or can be stored somewhere.

2. Yes, we usually represent these with a singleton instance (object) of a trait:

   case object EmptyNode extends Tree
   

3. There are a lot of algorithms out there, Breadth First Search and Depth First Search are the most common. It is a good exercise to implement them. But a bit of help on the Scala side, we usually pattern match on the left and right to see what we need to do next:

   tree: Tree match {
     case EmptyNode => // do nothing, return, etc.
     case Node(left, value, right) =>
       // Do inorder, preorder, postorder operation order
       // You will also probably be processing left and right as well
   }
   

4. No, your guess is right that using immutable case classes in a tree is quite hard to update, because if you update a leaf node then you must recreate everything above it. There are so called Lenses and Lens libraries that can help you with this, although they may be a bit more advanced. One popular one in Scala is Monocle.

---

It seems like you are just starting with programming or new to Scala so I would recommend using var-s instead of vals:

case class Node(var left: Tree, var value: String, var right: Tree) extends Tree

Also if your traits are sealed (sealed trait Tree) then the compiler will tell you if you didn't handle one of the subtypes in a pattern match.

EDIT:

Based on the comments start working with this:

sealed trait Tree
case class Node(var left: Tree, var value: String, var right: Tree, var parent: Tree) extends Tree
case object EmptyNode extends Tree