Building a tree from a stream with Scala

Solution 1

This solution works recursively and requires that all lines have already been read. You are always in the same row. If there are more lines, you create Tree

for this purpose. Basically it will create Tree

for the leaves first.

When you have them, you know that the first and the second Tree

form a new one Tree

. The second and third form a second new Tree

, etc. This is what it does sliding

.

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. The result is Option[Tree]

. None

is given when there is no value / no line at all. It does not deal with cases where the string might be garbled.

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)

      

        
        
        
      

    

that leads to:

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 (please ignore): I like it somehow zipped

now

Solution 2

This is the solution as you described it. It goes down from top to bottom and updates the tree after every insert. It has to follow the head though, because when we want to insert leaves we have to change all parent nodes, this reference is not stored in Tree

. I must admit that it all became useless with all these Option

s.

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

      

        
        
        
      

    

We can now use it with an iterator.

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