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)
}

walktree(someRootNode)

Edit - The list of nodes is taken from a database. Pulling the nodes into a proper tree would take too much time. I am pulling a flat list into memory and all I have is an association via node id's as pertains to parents and children.

Adding left/right node values allows me to get a snapshop of all children (and childrens children) with a single SQL query.

The calculation needs to run very quickly in order to maintain data integrity should parent-child associations change (which they do very frequently).

In addition to using the awesome Scala collections I've also boosted speed by using parallel processing for some pre/post filtering on the tree nodes. I wanted to find a more idiomatic way of tracking the left/right node values. After looking at the answers listed I have settled on this synthesised version:

def walktree(node: TreeNode) = {
    def walk(node: TreeNode, counter: Int): Int = {
        node.left = counter 
        node.right = 
          treeNodes 
          .filter( _.parentId == node.id)
          .foldLeft(counter+1) {
            (counter, curnode) => walk(curnode, counter) + 1
        }
        node.right
    }
    walk(node,1)
}