Build an immutable collection while traversing a binary tree

Question

I'm using the class MessageTree, below, to represent a binary tree that contains instances of Message, and I want to implement a method filter that returns a new MessageTree that contains all messages that satisfy a given predicate. I have a solution that uses a ListBuffer and I'm looking for a solution that builds an immutable collection, instead of a ListBuffer, while traversing the tree. Any insights are appreciated.

object scratchpad extends App {

  import scala.collection.mutable.ListBuffer

  // A class to represent messages
  class Message(val text: String, val user: String, val comments: Int) {
    override def toString: String =
      "User: " + user + "\n" +
        "Text: " + text + " [" + comments + " comments]"
  }

  /* --------------------------------------------------------------------- */

  abstract class MessageTree {

    type MessagePredicate = Message => Boolean

    def traverse(p: MessagePredicate, storage: ListBuffer[Message]) : Unit

    def filter(p: Message => Boolean): MessageTree = filterAcc(p, new Empty)

    def filterAcc(p: Message => Boolean, acc: MessageTree): MessageTree

    def incl(tweet: Message): MessageTree

    def foreach(f: Message => Unit): Unit

  }

  /* --------------------------------------------------------------------- */

  class Empty extends MessageTree {

    override def traverse(p: MessagePredicate, storage: ListBuffer[Message]): Unit = {}

    override def filterAcc(p: (Message) => Boolean, acc: MessageTree): MessageTree = acc

    def incl(tweet: Message): MessageTree = new NonEmpty(tweet, new Empty, new Empty)

    def foreach(f: Message => Unit): Unit = ()

  }

  /* --------------------------------------------------------------------- */

  class NonEmpty(elem: Message, left: MessageTree, right: MessageTree) extends MessageTree {

    override def traverse(p: MessagePredicate, storage: ListBuffer[Message]): Unit = {
      left.traverse(p, storage)
      if (p(elem)) storage += elem
      right.traverse(p, storage)
    }

    override def filterAcc(p: (Message) => Boolean, acc: MessageTree): MessageTree = {
      val tweet_collector = ListBuffer.empty[Message]
      traverse(p, tweet_collector)
      def loop(listBuffer: ListBuffer[Message], accum: MessageTree) : MessageTree = {
        if (listBuffer.isEmpty) accum
        else loop(listBuffer.tail, accum incl listBuffer.head)
      }
      loop(tweet_collector, acc)
    }

    def incl(x: Message): MessageTree = {
      if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
      else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
      else this
    }

    def foreach(f: Message => Unit): Unit = {
      left.foreach(f)
      f(elem)
      right.foreach(f)
    }

  }

  /* --------------------------------------------------------------------- */
  /* Test
  /* --------------------------------------------------------------------- */
  val keyword_list: List[String] = "one" :: "three" :: "five" :: "seven" :: "nine" :: Nil

  def search_predicate(msg: Message): Boolean = {
    keyword_list.exists(msg.text.contains(_))
  }

  val msg_00 = new Message("zero", "John_00", 50)
  val msg_01 = new Message("one", "John_01", 10)
  val msg_02 = new Message("two", "John_02", 20)
  val msg_03 = new Message("three", "John_03", 30)
  val msg_04 = new Message("four", "John_04", 40)
  val msg_05 = new Message("five", "John_05", 50)

  val tmp_message_tree = new NonEmpty(msg_00, new Empty, new Empty)
  val message_tree = tmp_message_tree incl msg_01 incl msg_02 incl msg_03 incl msg_04 incl msg_05

  println("All messages")
  message_tree foreach println

  println("Filtered messages")
  (message_tree filter search_predicate) foreach println


}

The output is

All messages

User: John_05
Text: five [50 comments]
User: John_04
Text: four [40 comments]
User: John_01
Text: one [10 comments]
User: John_03
Text: three [30 comments]
User: John_02
Text: two [20 comments]
User: John_00
Text: zero [50 comments]

Filtered messages

User: John_05
Text: five [50 comments]
User: John_01
Text: one [10 comments]
User: John_03
Text: three [30 comments]

Answer 1

You're almost there: you need only to change the traverse like so:

def traverse(p: MessagePredicate):List[Message] = {
  left.traverse(p) ++ 
  (if (p(elem)) List(elem) else List()) ++
  right.traverse(p)
}  

This solution is simple but it utilizes too much list concatination which is expensive. Another approach is to use accumulator to reduce concatinations:

def traverse(p: MessagePredicate, acc:List[Message]):List[Message] = {
  val r = right.traverse(acc)
  left.traverse(p, if(p (elem)) elem::r else r)
}

and for empty node:

def traverse(p: MessagePredicate, acc:List[Message]):List[Message] = acc