Ken (Chanoch) Bloom's Blog

29th December 2009

Tree Traversals in Scala

Just documenting an algorithm that I don't want to keep figuring out all over again every time I need it.

Supposing we want to perform a depth-first search of a tree in Scala, labeling each node with a number, and the number of its parent:

case class Tree(children:Tree*){
   var id:Int = -1
   var parent:Int = -1
}

def identify(parentID:Int)(myID:Int,tree:Tree):Int={
   tree.parent=parentID
   tree.id=myID
   tree.children.foldLeft(myID+1)(identify(myID)_)
}

Supposing we want to label the tree nodes with nested left-and-right keys, as well as the left key of the parent:

case class LRTree(children:LRTree*){
  var left:Int = -1
  var right:Int = -1
  var parentLeft:Int = -1
}

def identifyLR(parentLeft:Int)(myLeft:Int,tree:LRTree):Int={
   tree.parentLeft=parentLeft
   tree.left=myLeft
   tree.right=tree.children.foldLeft(myLeft+1)(identifyLR(myLeft)_)
   tree.right+1
}
Permalink | scala.
My Website Archives

Tags