BFS tree traversal Scala

Question

I would love some feedback on the following code for BFS traversal in a binary tree. Is there a cleaner way to write this?

abstract class Tree[+T] 
case class Node[T](value:T,var left:Tree[T],var right:Tree[T]) extends Tree[T] 
case object End extends Tree[Nothing]
def bfs_v2[T](node:Node[T]):List[T] = {
 def enQueueNext(queue: Queue[Node[T]], aNode: Tree[T]) {
 aNode match {
 case internalNode: Node[T] => queue += internalNode
 case End => {}
 }
 }
 def bfs_visit(queue:Queue[Node[T]],visited:List[T]):List[T] = {
 if(queue.isEmpty){
 visited
 }
 else{
 val currentNode = queue.dequeue()
 enQueueNext(queue, currentNode.left)
 enQueueNext(queue,currentNode.right)
 bfs_visit(queue,currentNode.value :: visited )
 }
 }
 val aQueue = new mutable.Queue[Node[T]]()
 bfs_visit(aQueue += node,List[T]()).reverse
 }

Answer 1

As pointed out by @Bob Dalgleish, you mix mutable/immutable. You also mix pattern matching (enQueueNext) with if/else (bfs_visit). You also mix camel case notation (enQueueNext) with underscore notation (bfs_visit).

trait would be more appropriate for Tree than abstract class. You don't really need Tree, as I show in my example, but that is debatable. You don't really need a queue either.

You can make very succinct code with Scala. In my example below, the recursive BFS algorithm is basically a single line: bfsLoop(nextLayer.map(_.value) :: accum, nextLayer.flatMap(_.childrenLeftRight)).

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))
}

I also put this code for a separate codereview after posting it as an answer.

• Matt Foxx Duncan: In the bfs method how would you keep track of each level of depth? Say I wanted to filter by level or return something like Map[Depth,List[Node]]
• toto2: It's nearly already done from the way I built my method. In bfsLoop(accum: List[List[T]],...), the accum variable is the list of nodes at each depth. Instead of returning accum.reverse.flatten, just do something with zipWithIndex and toMap to transform it to a Map[Depth, List[Node]].

Answer 2

Several points:

1. Why do you have var fields for your case class? Unless you have a good, conscious reason for doing so, you should leave them as vals.
2. In enqueue, you refer to Queue while you have declared the actual item as mutable.Queue. You should be consistent in your declaration. While the code will work, a reader will be confused how the += operator works on a queue, since immutable data is the norm.
3. If you want to use mutable data structures, you might consider creating your list as mutable and appending to it. That way you can skip the reverse call.
4. You could make your queue serve double duty. Since it will contain all of your nodes in the order of visiting, you could traverse the queue without removing any from the front, but just adding unvisited nodes to the back. Once you reach the end of the queue, you can extract the values in order by queue.map(_.value).

• smk: For comment 1. How do I edit the left , right child of a Node if I dont give it as var?
• Bob Dalgleish: If you have a requirement to edit the nodes, then, by all means, make them var. I'm just saying that, in Scala, there are substantial benefits to making data structures immutable.