BFS and DFS tree traversal

Question

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?

Answer 1

Any comments are welcomed, but I am mostly annoyed by terminalNode

From my opinion, it's more natural to provide default values for case classes:

case class Node[+T](value: T, left: Option[Node[T]] = None, right: Option[Node[T]] = None) {//...

Then you can simply use Node(42) anywhere in your code.

Node looks like a monad. Could I get all other operations such as flatMap and foldLeft for free somehow?

Typically, any methods in Monads are based on flatMap and unit methods. Therefore you need to implement flatMap method, as unit method you already have (Node.apply).

flatMap needs to accept a method, which returns new instance of Node, e.g. def flatMap[V](f: T => Node[V]): Node[V]. Then it should look like the following:

def flatMap[V](f: T => Node[V]): Node[V] = {
    f(value).copy(
      left = left.map(_.flatMap(f)),
      right = right.map(_.flatMap(f))
    )
}

And it you create a new test, it produce the same output, as for map:

println("map: " + tree1.map(i => s"Hello$i"))
println("fmap: " + tree1.flatMap(i => Node(s"Hello$i"))) //will be the same outputs

But, you should handle cases, when f(value) may return new node with existing left and/or right values, otherwise the implementation above may override the result. You need to consider this in your final implementation.

Then, according to the rule of map, it can be present as map(f) = fmap unit f, so you can create method map2 with flatMap:

def map2[V](f: T => V): Node[V] =
  flatMap(t => Node(f(t)))

Then you will have the same outputs:

println("map: " + tree1.map(i => s"Hello$i"))
println("map2: " + tree1.map2(i => s"Hello$i")) //will be the same outputs

Regarding foldLeft: typically you can almost everything implement with foldLeft, but not otherwise. So we need to understand, what foldLeft should do (DSF?), and then we can express other methods with this.

Also couple notes, I'd change (it's arguable, of course, but worth considering):

• Instead of left.map(l => l.map(f) I'd use left.map(_.map(f))
• tree.map(t => (output = t :: output)) this can be replaced with mutable ArrayBuffer for 2 reasons: it should be slightly faster and slightly more well-looking.

Consider this code:

 def dfs2[T](tree: Node[T]): List[T] = {
   val output = ArrayBuffer[T]()
   tree.map(output += _)
   output.toList
 }

And outputs again will be the same:

println("dfs: " + dfs(tree1))
println("dfs2: " + dfs2(tree1)) //will be the same outputs

Hope that helps.