Building a tree from Stream using Scala

Question

I want to build a tree which is read from a file of random height in this exact format,

       1
      2 3
     4 5 6
    . . . .
   . . . . .

using the following structure

case class Tree[+T](value : T, left :Option[Tree[T]], right : Option[Tree[T]])

The challenge I am facing is I have to read until the last line before I can build the tree because left and right is read only. The way I tried was,

1. Read the first line, create an node with a value (1) with left and right set to None.
2. Read the second line, create nodes with values (2) and (3), left and right set to None. This time, a new node (1) is created with left = node(2) and right = node(3).
3. Read the third line, create nodes with values (4), (5) and (6), with left and right set to None. Create new node(2) and node(3) with node(2) -> node(4) and node(5) and node(3) -> node(5) and node(6) and finally, node(1) -> new node(2) and node(3)
4. Repeat until end of line.

At the end of it, I should have this relationship,

         1
        /  \
       2    3
      / \   / \
     4   5 5  6
    / \ /\ /\ / \
   .  .. . .. .  .

Any good advice for me? Thanks

Answer 1

Solution 1

This solution works recursively and needs all lines to be already read. You are always at one row. If there are more rows, you create the Trees for these first. Basically it will first create Trees for the leaves.

When you have them, you know that the first and the second Tree form the new Tree. The second and the third form the second new Tree and so on. This is what sliding does.

As an example for sliding: List(1,2,3,4).sliding(2) = List(List(1,2),List(2,3),List(3,4))

In this solution I did not pay attention to efficiency though. The result is an Option[Tree]. None is yielded in case where there is no value/no line at all. It does not deal with cases where the string might be malformed.

case class Tree[+T](value : T, left :Option[Tree[T]], right : Option[Tree[T]])

def buildTree[T](lines: IndexedSeq[IndexedSeq[T]]) = {
  def recurse[T](lines: IndexedSeq[IndexedSeq[T]]): IndexedSeq[Tree[T]] = lines match {
    case line +: IndexedSeq() => line.map(Tree(_, None, None))
    case line +: rest => {
      val prevTrees = recurse(rest)
      (line, prevTrees.sliding(2).toIndexedSeq).zipped
      .map{case (v, IndexedSeq(left, right)) => Tree(v, Some(left), Some(right))}
    }
    case _ => IndexedSeq.empty
  }
  recurse(lines).headOption
}

Example:

val input = """1
2 3
4 5 6""".stripMargin

val lines = input.lines.map(_.filterNot(_ == ' ').toIndexedSeq).toIndexedSeq
//Vector(Vector(1), Vector(2, 3), Vector(4, 5, 6))

val result = buildTree(lines)

which results in:

Some(Tree(1,Some(Tree(2,Some(Tree(4,None,None)),Some(Tree(5,None,None)))),Some(Tree(3,Some(Tree(5,None,None)),Some(Tree(6,None,None))))))

Random insider (ignore please): I kinda like zipped now

Solution 2

This is a solution like you described it. It goes down from top to bottom and updates the tree after each insertion. It has to keep track of the head though, because when we want to insert leaves we have to modify all parent nodes, which reference is not stored in Tree. I have to admit that things got pretty messy with all these Options.

def buildTree2[T](lines: Iterator[IndexedSeq[T]]) = {
  @tailrec
  def loop(current: IndexedSeq[Tree[T]], head: Option[Tree[T]] = None): Option[Tree[T]] = {
    if(lines.hasNext) {
      val newTrees = lines.next.map(v => Option(Tree(v, None, None)))
      if(!current.isEmpty) {
        val h = (current, newTrees.sliding(2).toIndexedSeq).zipped.foldLeft(head.get) {
          case (nextHead, (parent, IndexedSeq(left, right))) => updateTree(nextHead, parent, Tree(parent.value, left, right))
        }
        loop(newTrees.flatten, Some(h))
      } else loop(newTrees.flatten, newTrees.head)
    } else head
  }

  def updateTree[T](head: Tree[T], target: Tree[T], replacement: Tree[T]): Tree[T] = {
    if(head eq target) {
      replacement
    } else head match {
      case Tree(v, Some(l), Some(r)) => Tree(v, Option(updateTree(l, target, replacement)), Option(updateTree(r, target, replacement)))
      case _ => head
    }
  }
  loop(IndexedSeq.empty)
}

Now we can use it with an iterator.

val lines = input.lines.map(_.filterNot(_ == ' ').toIndexedSeq)
buildTree2(lines)