Tree searches

tree-search-algorithms.scala

package com.ryangantt.scala

import scala.collection.mutable.Queue
import scala.collection.mutable.ArrayBuffer

abstract class Element[+T]
case class Node[T](val left: Element[T], val right: Element[T], val value: Leaf[T]) extends Element[T]
case class Leaf[T](val value: T) extends Element[T]
case object Sentinel extends Element

object Node {
  val tree = Node(
    Node(
      Node(
        Sentinel, 
        Leaf("leftleftright"), 
        Leaf("leftleft")
      ), 
      Leaf("leftright"), 
      Leaf("left")
    ), 
    Node(
      Node(
        Sentinel, 
        Leaf("rightleftright"), 
        Leaf("rightleft")
      ), 
      Leaf("rightright"), 
      Leaf("right")
    ), 
    Leaf("root")
  )

  def main(args: Array[String]) {
    println("Breadth first: " + printResult(breadthFirst(tree)));
    println("Depth first: " + printResult(depthFirst(tree)));
  }

  def depthFirst(tree: Element[String]): Array[Element[String]] = {
    def aux(node: Element[String], nodes: ArrayBuffer[Element[String]]): Array[Element[String]] = {
      node match {
        case Node(left, right, _) => {
          nodes += left
          nodes ++= aux(left, ArrayBuffer())
          nodes += right
          nodes ++= aux(right, ArrayBuffer())
        }
        case _ => ;
      }
      Array(nodes : _*)
    }
    aux(tree, ArrayBuffer(tree))
  }

  def breadthFirst(tree: Element[String]): Array[Element[String]] = {
    val list = Queue(tree)
    val all = ArrayBuffer(tree)

    while (!list.isEmpty) {
      list.dequeue match {
        case Node(left, right, _) => {
          list.enqueue(left, right)
          all += (left, right)
        }
        case _ => ;
      }
    }
    Array(all : _*)
  }

  def printResult(result: Array[Element[String]]): String = {
    val builder = new StringBuilder
    for (node <- result) {
      node match {
        case Node(_, _, Leaf(value)) => {
          builder.append(value + " ")
        }
        case Leaf(value) => {
          builder.append(value + " ")
        }
        case _ => ;
      }
    }
    builder.toString
  }
}

Breadth first: root left right leftleft leftright rightleft rightright leftleftright rightleftright
Depth first: root left leftleft leftleftright leftright right rightleft rightleftright rightright