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:
How can I also include a pointer to a parent?
Can I have left and right point to null in any way? Or the parent pointer for the root node?
How can I actually traverse the tree?
Is it easy to update the values of a node?
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.
Yes, we usually represent these with a singleton instance (
object
) of a trait: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
andright
to see what we need to do next: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 ofval
s: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: