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.

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