Change node in Scala case class tree

Question

Assume that I have some tree build using case classes, something like that:

abstract class Tree
case class Branch(b1:Tree,b2:Tree, value:Int) extends Tree
case class Leaf(value:Int) extends Tree
var tree = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6))

And now I want to build a method to change the node with some id to another node. It's easy to find this node, but I don't know how to change it. Is there any simply way to do that?

Answer 1

That's a very interesting question! As others have already noted, you have to change the entire path from root to the node you want to change. Immutable maps are very similar, and you may learn something looking at Clojure's PersistentHashMap.

My recommendations are:

• Change Tree to Node. You even call it node in your question, so this is probably a better name.
• Pull value up to the base class. Once again, you talk about that in your question, so this is probably the right place for it.
• In your replace method, be sure that if neither a Node nor its children changes, don't create a new Node.

Comments are in the code below:

// Changed Tree to Node, b/c that seems more accurate
// Since Branch and Leaf both have value, pull that up to base class
sealed abstract class Node(val value: Int) {
  /** Replaces this node or its children according to the given function */
  def replace(fn: Node => Node): Node

  /** Helper to replace nodes that have a given value */
  def replace(value: Int, node: Node): Node =
    replace(n => if (n.value == value) node else n)
}

// putting value first makes class structure match tree structure
case class Branch(override val value: Int, left: Node, right: Node)
     extends Node(value) {
  def replace(fn: Node => Node): Node = {
    val newSelf = fn(this)

    if (this eq newSelf) {
      // this node's value didn't change, check the children
      val newLeft = left.replace(fn)
      val newRight = right.replace(fn)

      if ((left eq newLeft) && (right eq newRight)) {
        // neither this node nor children changed
        this
      } else {
        // change the children of this node
        copy(left = newLeft, right = newRight)
      }
    } else {
      // change this node
      newSelf
    }
  }
}

Answer 2

As your tree structure is immutable, you have to change the whole path, from node up to the root. when you visit your tree, keep a list of the visited nodes, then, update all the node up to the root, with the copy method, as suggested by pr10001.