5
\$\begingroup\$

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
  }
\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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]] \$\endgroup\$ Nov 25, 2014 at 19:15
  • 1
    \$\begingroup\$ 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]]. \$\endgroup\$
    – toto2
    Nov 25, 2014 at 22:50
3
\$\begingroup\$

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).
\$\endgroup\$
2
  • \$\begingroup\$ For comment 1. How do I edit the left , right child of a Node if I dont give it as var? \$\endgroup\$
    – smk
    Sep 14, 2014 at 18:49
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 15, 2014 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.