How can I make this method more Scalalicious

Question

I have a function that calculates the left and right node values for some collection of treeNodes given a simple node.id, node.parentId association. It's very simple and works well enough...but, well, I am wondering if there is a more idiomatic approach. Specifically is there a way to track the left/right values without using some externally tracked value but still keep the tasty recursion. ``` /* * A tree node */ case class TreeNode(val id:String, val parentId: String){ var left: Int = 0 var right: Int = 0 } /* * a method to compute the left/right node values */ def walktree(node: TreeNode) = { /* * increment state for the inner function */ var c = 0 /* * A method to set the increment state */ def increment = { c+=1; c } // poo /* * the tasty inner method * treeNodes is a List[TreeNode] */ def walk(node: TreeNode): Unit = { node.left = increment /* * recurse on all direct descendants */ treeNodes filter( _.parentId == node.id) foreach (walk(_)) node.right = increment } walk(node) } w…

Accepted Answer

Your code appears to be calculating an in-order traversal numbering.

I think what you want to make your code better is a `fold` that carries the current value downward and passes the updated value upward. Note that it might also be worth it to do a `treeNodes.groupBy(_.parentId)` before `walktree` to prevent you from calling `treeNodes.filter(...)` every time you call `walk`.

```
val treeNodes = List(TreeNode("1","0"),TreeNode("2","1"),TreeNode("3","1"))

val treeNodeMap = treeNodes.groupBy(_.parentId).withDefaultValue(Nil)

def walktree2(node: TreeNode) = {
  def walk(node: TreeNode, c: Int): Int = {
    node.left = c
    val newC = 
      treeNodeMap(node.id)         // get the children without filtering
        .foldLeft(c+1)((c, child) => walk(child, c) + 1)
    node.right = newC
    newC
  }

walk(node, 1)
}
```

And it produces the same result:

```
scala> walktree2(TreeNode("0","-1"))
scala> treeNodes.map(n => "(%s,%s)".format(n.left,n.right))
res32: List[String] = List((2,7), (3,4), (5,6))
```

That said, I would completely rewrite your code as follows:

```
case class TreeNode(        // class is now immutable; `walktree` returns a new tree
  id: String,
  value: Int,               // value to be set during `walktree` 
  left: Option[TreeNode],   // recursively-defined structure
  right: Option[TreeNode])  //   makes traversal much simpler

def walktree(node: TreeNode) = {
  def walk(nodeOption: Option[TreeNode], c: Int): (Option[TreeNode], Int) = {
    nodeOption match {
      case None => (None, c)  // if this child doesn't exist, do nothing
      case Some(node) =>      // if this child exists, recursively walk
        val (newLeft, cLeft) = walk(node.left, c)        // walk the left side
        val newC = cLeft + 1                             // update the value
        val (newRight, cRight) = walk(node.right, newC)  // walk the right side
        (Some(TreeNode(node.id, newC, newLeft, newRight)), cRight)
    }
  }

walk(Some(node), 0)._1
}
```

Then you can use it like this:

```
walktree(
  TreeNode("1", -1,
    Some(TreeNode("2", -1,
      Some(TreeNode("3", -1, None, None)),
      Some(TreeNode("4", -1, None, None)))),
    Some(TreeNode("5", -1, None, None))))
```

To produce:

```
Some(TreeNode(1,4,
  Some(TreeNode(2,2,
    Some(TreeNode(3,1,None,None)),
    Some(TreeNode(4,3,None,None)))),
  Some(TreeNode(5,5,None,None))))
```

How can I make this method more Scalalicious

Solution

Problem