Scala, trees, pattern matching and tree recursion

Hi! Long time no see...

Well after some outage due to Holiday (road trip around Europe and down to the Swiss Alps!), work commitments and some personal things to deal with, I'm back again.

I thought I'd start with some stuff on Tree structures, whilst continuing on with Scala too. The following code illustrates some good examples of case classes and pattern matching, along with extensive use of Some, None and Option (Scala's improved way of dealing with optional types, rather than relying on null everywhere).

The following code defines a simple recursive binary tree definition as a case class, using option to define the left and right children.

case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

The above definition defines a tree recursively, exactly as a tree is defined as a data structure in computer science. Each tree node has a value of type T and an Optional left and right child node (bin tree). The +T makes the Tree type covarient about T, which is a generally useful property of a Tree.

A few helper functions are used that make life a little easier when working with Option types, by extracting the value or providing a safe default when no value exists. These help keep the code a little tidy and manageable.

 /**
  * Helper function: For o return f: A => Int if Some or 0 if None
  *   also could try opt map f getOrElse 0
  */
 def zeroIfNone[A](o: Option[A], f: A => Int): Int = o match {
   case None => 0
   case Some(x) => f(x)
 }

 /**
  * Helper function: Return value of function provided if Some, or 0 otherwise
  */
 def zeroIfNoneVal[A](o: Option[A], n: => Int) = zeroIfNone[A](o, _ => n)

 /**
  * Helper function: Default to provided value if option is None
  */
 def defaultIfNone[A](o: Option[A], f: A => Int, d : Int): Int = o match {
   case None => d
   case Some(x) => f(x)
 }

The example code demonstrates preorder, inorder and postorder recursive tree traversal (which are all simple permutations of a basic depth first search), applying the provided unit function to each node as it is visited.

Recall that the preorder, inorder and postorder functions are defined as follows:

• PreOrder - visit parent node, left and then right child node
• InOrder - visit left, parent and then right nodes
• PostOrder - visit left, right and then parent node

Using recursion and the call stack, depth first search based tree traversal is very simple and concise. The basic DFS inorder traversal looks like:

 /**
  * Perform an inorder tree traversal using the provided Tree[A] => Unit function
  */
 def inOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     if (x.left != None) inOrder(x.left, f)
     f(x)
     if (x.right != None) inOrder(x.right, f)
 }

The breadth first search algorithm is perhaps more interesting. This uses a List as a basic FIFO queue to provide the breadth first search tree traversal:

 /**
  * Breadth first search on a tree, a list is used as a basic fifo queue to
  *   give the bfs traversal
  */
 def breadthFirstSearch[A](t: Tree[A], f: Tree[A] => Unit): Unit = {
   def bfs(ts: List[Tree[A]]): Unit = ts match {
     case Nil => // ignore
     case _ =>
       val children = for{tree <- ts         
         Some(child) <- List(tree.left, tree.right)}         
         yield child      
     ts map f     
     bfs(children)   
   }     
   bfs(List(t))  
 } 

The example also shows a treeFold function. Whether this is a useful function as-is is perhaps debatable, but it makes for an interesting example. The code traverses the tree in a DFS inorder traversal and applies the mapping function f : A -> B and then it applies the join function j : B, B -> B to combine the results of the tree map. In this way the function is similar to say flatMap where a list is mapped and then flattened into a single list, or perhaps more closely to foldLeft/foldRight where items in a list a joined into a single resulting value.

 /**
  * Fold up a tree into a single value, using provided map and join functions
  */
 def treeFold[A, B](t: Option[Tree[A]],
                    f: Option[Tree[A]] => Option[B],
                    j: (Option[B], Option[B]) => Option[B]) : Option[B] = t match {

   case None => None
   case Some(x) => j(j(f(t), treeFold(x.left, f, j)), treeFold(x.right, f, j))
 }

Some utility functions are also defined, to return the size and depth of the tree for illustration of how this can be achieved.

In summary Scala can quite elegantly represent Tree data structures, using case classes and operate over them using pattern matching and higher order functions to provide powerful and concise support for trees and the operations that can be performed on them.

Some additional things that could be done here would be to provide an example of a binary search and perhaps insertion, update and delete too. A job for another followup blog perhaps...


The full example code (is complete and self contained) is as follows:

package trees

// Define a recursive Bin Tree structure
case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])

object TreeObj {

 /**
  * Helper function: For o return f: A => Int if Some or 0 if None
  *   also could try opt map f getOrElse 0
  */
 def zeroIfNone[A](o: Option[A], f: A => Int): Int = o match {
   case None => 0
   case Some(x) => f(x)
 }

 /**
  * Helper function: Return value of function provided if Some, or 0 otherwise
  */
 def zeroIfNoneVal[A](o: Option[A], n: => Int) = zeroIfNone[A](o, _ => n)

 /**
  * Helper function: Default to provided value if option is None
  */
 def defaultIfNone[A](o: Option[A], f: A => Int, d : Int): Int = o match {
   case None => d
   case Some(x) => f(x)
 }

 /**
  * Return the size of the tree
  */
 def size[A](t : Option[Tree[A]]) : Int = t match {

   case None => 0
   case Some(x) =>
     zeroIfNoneVal(x.left, size(x.left)) + zeroIfNoneVal(x.right, size(x.right)) + 1
     //zeroIfNone(x.left, (_:Tree[Any]) => (size(x.left))) +
     //zeroIfNone(x.right, (_:Tree[Any]) => (size(x.right))) + 1
 }

 /**
  * Alternative size using nested function
  */
 def size2[A](t : Option[Tree[A]]) : Int = {

   def sizeB(b : Option[Tree[A]]) : Int = b match {
     case None => 0
     case Some(x) => size(b);
   }

   t match {
     case None => 0
     case Some(x) =>
       sizeB(x.left) + sizeB(x.right) + 1
   }
 }

 /**
  * Return the max depth of the tree
  */
 def depth[A](t : Option[Tree[A]]) : Int = t match {

   case None => 0
   case Some(x) =>
     Math.max(zeroIfNoneVal(x.left, depth(x.left)), zeroIfNoneVal(x.right, depth(x.right))) + 1
 }

 /**
  * Alternative deptch, return the max depth of the tree using nested function
  */
 def depth2[A](t : Option[Tree[A]]) : Int = {

   def depthB(b : Option[Tree[A]]) : Int = b match {
     case None => 0
     case Some(x) => depth(b);
   }

   t match {

     case None => 0
     case Some(x) =>
       Math.max(depthB(x.left), depthB(x.right)) + 1
   }
 }

 /**
  * Breadth first search on a tree, a list is used as a basic fifo queue to
  *   give the bfs traversal
  */
 def breadthFirstSearch[A](t: Tree[A], f: Tree[A] => Unit): Unit = {
   def bfs(ts: List[Tree[A]]): Unit = ts match {
     case Nil => // ignore
     case _ =>
       val children = for{tree <- ts           Some(child) <- List(tree.left, tree.right)}           yield child       ts map f       bfs(children)     }      bfs(List(t))   }    /**    * Sum up the elements of a numeric tree    */   def sumTree[A <: Int](t: Option[Tree[A]]) : Int = t match {      case None => 0
   case Some(x) =>
     sumTree(x.left) + sumTree(x.right) + x.value
 }

 /**
  * Fold up a tree into a single value, using provided map and join functions
  */
 def treeFold[A, B](t: Option[Tree[A]],
                    f: Option[Tree[A]] => Option[B],
                    j: (Option[B], Option[B]) => Option[B]) : Option[B] = t match {

   case None => None
   case Some(x) => j(j(f(t), treeFold(x.left, f, j)), treeFold(x.right, f, j))
 }

 /**
  * Perform an inorder tree traversal using the provided Tree[A] => Unit function
  */
 def inOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     if (x.left != None) inOrder(x.left, f)
     f(x)
     if (x.right != None) inOrder(x.right, f)
 }

 /**
  * Perform a preorder tree traversal using the provided Tree[A] => Unit functio
  */
 def preOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     f(x)
     if (x.left != None) inOrder(x.left, f)
     if (x.right != None) inOrder(x.right, f)
 }

 /**
  * Perform a postorder tree traversal using the provided Tree[A] => Unit functio
  */
 def postOrder[A](t: Option[Tree[A]], f: Tree[A] => Unit) : Unit = t match {

   case None =>
   case Some(x) =>
     if (x.left != None) inOrder(x.left, f)
     if (x.right != None) inOrder(x.right, f)
     f(x)
 }

 /**
  * build tree and run tree functions on it
  */
 def main(args : Array[String]) {

   /* Test Tree structure

               1
              / \
             2   3
            / \ / \
           4  x 5  6
         
   */

   // build a tree
   val myTree = Tree(1,
     Some(Tree(2,
       Some(Tree(4, None, None)),
         None
       )
     ),
     Some(Tree(3,
       Some(Tree(5, None, None)),
         Some(Tree(6, None, None))
       )
     )
   )

   printBfsTree(myTree)

   println("Size = " + size(Some(myTree)))

   println("Depth = " + depth(Some(myTree)))

   println("Sum = " + sumTree(Some(myTree)))
  
   var sum = treeFold[Int, Int](
               Some(myTree),
               (t: Option[Tree[Int]]) => t match { case None => Some(0); case Some(x) => Some(x.value) },
               (x: Option[Int], y: Option[Int]) =>
                 Some(zeroIfNone[Int](x, (x:Int) => x) + zeroIfNone[Int](y, y => y))
             )

   var mult = treeFold[Int, Int](
               Some(myTree),
               (t: Option[Tree[Int]]) => t match { case None => Some(0); case Some(x) => Some(x.value) },
               (x: Option[Int], y: Option[Int]) =>
                 Some(defaultIfNone[Int](x, (x:Int) => x, 1) * defaultIfNone[Int](y, y => y, 1))
              )

   println("Sum Result = " + sum)
   println("Mult Result = " + mult)

   println("InOrder = ")
   inOrder(Some(myTree), (t: Tree[Any]) => println(t.value))

   println("PreOrder = ")
   preOrder(Some(myTree), (t: Tree[Any]) => println(t.value))

   println("PostOrder = ")
   postOrder(Some(myTree), (t: Tree[Any]) => println(t.value))
 }

 /**
  * Print a tree using BFS, passing in print unit function
  */
 def printBfsTree[A](tree: Tree[A]) {

   breadthFirstSearch(tree, (t: Tree[A]) => println(t.value))
 }
}

.