I posted some code as part of an answer to another question and I thought it would be a good idea to get that code reviewed also.
Any comments are welcomed, but I am mostly annoyed by terminalNode
. It is basically a slightly convenient factory method, but I think it should either be renamed to something more enlightening, or something entirely different should be done.
object TreeTraversal extends App {
case class Node[+T](value: T, left: Option[Node[T]], right: Option[Node[T]]) {
def map[V](f: T => V): Node[V] =
Node(f(value), left.map(l => l.map(f)), right.map(r => r.map(f)))
def childrenLeftRight: List[Node[T]] = List(left, right).flatten
}
def terminalNode[T](value: T) = Node(value, None, None)
def dfs[T](tree: Node[T]): List[T] = {
var output = List[T]()
tree.map(t => (output = t :: output))
output.reverse
}
def bfs[T](tree: Node[T]): List[T] = {
@tailrec
def bfsLoop(accum: List[List[T]], nextLayer: List[Node[T]]): List[T] = nextLayer match {
case Nil => accum.reverse.flatten
case _ => bfsLoop(nextLayer.map(_.value) :: accum, nextLayer.flatMap(_.childrenLeftRight))
}
bfsLoop(List[List[T]](), List(tree))
}
val tree1 = Node[Int](6, Some(Node(13, Some(terminalNode(101)), None)), Some(Node(42, Some(terminalNode(666)), Some(terminalNode(65)))))
println("map: " + tree1.map(i => s"Hello$i"))
println("dfs: " + dfs(tree1))
println("bfs: " + bfs(tree1))
}
Node
looks like a monad. Could I get all other operations such as flatMap and foldLeft for free somehow?