Deserialize a binary tree breadth-first in Functional Programming

Question

I had an imperative program which deserializes to a Binary Tree from an array. Its a BFS algorithm. I was wondering how to do this in Scala with functional programming concepts.

class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
  val value: Int = _value
  val left: TreeNode = _left
  val right: TreeNode = _right
}
def createTree(list: Array[Int]): TreeNode = ???

For reference this is the imperative version in Javascript. The algorithm is described here. https://support.leetcode.com/hc/en-us/articles/360011883654-What-does-1-null-2-3-mean-in-binary-tree-representation-

class TreeNode {
  constructor(val){
    this.val = val;
    this.left = this.right = null;
  }
}

function makeTree(arr){
  let root = new TreeNode(arr[0]);
  let q = [root];

  let index = 1;
  while(q.length){
    let node = q.splice(0,1)[0];
    if(arr[index] != null){
      node.left = new TreeNode(arr[index]);
      q.push(node.left);
    }
    index++;

    if(arr[index] != null){
      node.right = new TreeNode(arr[index]);
      q.push(node.right);
    }
    index++;
  }
  return root;
}

Answer 1

First of all, you can use a case class to simplify your tree class, and you should use Option instead of null:

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

Next, the main trouble here is because your tree is immutable, it needs to be built with a depth-first post-order traversal, and your serialization format requires a breadth-first level-order traversal. So you first have to deserialize to a data structure that can then be traversed in depth-first order. The following uses a Map from (row, column) to the node value:

@scala.annotation.tailrec
private def bfsTraverse(
    serialized: List[Option[Int]],
    queue: Queue[(Int, Int)],
    map: Map[(Int, Int), Int]): Map[(Int, Int), Int] = {
  val ((row, col), queueTail) = queue.dequeue
  if (serialized.isEmpty) {
    map
  } else if (serialized.head.isEmpty) {
    bfsTraverse(serialized.tail, queueTail, map)
  } else {
    val newQueue = queueTail.enqueueAll(List((row + 1, col * 2), (row + 1, col * 2 + 1)))
    val newMap = map + ((row, col) -> serialized.head.get)
    bfsTraverse(serialized.tail, newQueue, newMap)
  }
}

Now you can use the output of that function to build your Tree:

private def buildTree(row: Int, col: Int, map: Map[(Int, Int), Int]): Option[Tree] = {
  map.get((row, col)).map{value =>
    Tree(value, buildTree(row + 1, col * 2, map), buildTree(row + 1, col * 2 + 1, map))
  }
}

Answer 2

This solution is a bit verbose but uses some functional concepts and defines the data structures thoroughly.

• The algorithm you provided works better with mutable nodes. It's possible to have a shorter solution with just one mutable class, but here, there are two versions (one node class with mutable left/right and the other completely immutable).
• Case classes automatically provide a lot of useful features such as comparison and friendly print-out
• The processValues function tail-recursively performs the tasks equivalent to the makeTree function you provided.
• The @tailrec annotation tells the compiler to check that the function is tail recursive.
• Pattern matching using the match and case keywords replace checking for null-ness or different subtypes, and the compiler can check for a non-exhaustive match clause.
• The App trait allows you to easily make an object (static class) into an entrypoint to run some examples.

import scala.annotation.tailrec

sealed trait TreeNode[T]
sealed trait MutableTreeNode[T]
object MutableTreeNode {
  final case class Empty[T]() extends MutableTreeNode[T]
  case class Branch[T](val value: T) extends MutableTreeNode[T] {
    protected var left: MutableTreeNode[T] = Empty()
    protected var right: MutableTreeNode[T] = Empty()
    def setLeft(newLeft: T): Branch[T] = {
      left = Branch(newLeft)
      left.asInstanceOf[Branch[T]] // shouldn't be necessary but compiler requires it
    }
    def setRight(newRight: T): Branch[T] = {
      right = Branch(newRight)
      right.asInstanceOf[Branch[T]]
    }
    override def toString: String = this.toImmutable().toString

    /* converts given node to immutable version */
    private def toImmutable(node: MutableTreeNode[T]): TreeNode[T] = {
      node match {
        case Empty() => TreeNode.Empty()
        case b@Branch(value) => TreeNode.Branch(value, toImmutable(b.left), toImmutable(b.right))
      }
    }
    def toImmutable():TreeNode[T] = toImmutable(this)
  }

  /**
    * Modifies nodes inside of queue
    */
  @tailrec def processValues[T](values: Seq[Option[T]], queue: Seq[MutableTreeNode.Branch[T]]): Unit = {
    (queue, values) match {
      case (Nil, _) => ()
      case (_, Nil) => ()
      case (qHead :: qTail, Some(vLeft) :: Some(vRight) :: vTail) =>
        processValues(vTail, qTail :+ qHead.setLeft(vLeft) :+ qHead.setRight(vRight))
      case (qHead :: qTail, Some(vLeft) :: None :: vTail) =>
        processValues(vTail, qTail :+ qHead.setLeft(vLeft))
      case (qHead :: qTail, None :: Some(vRight) :: vTail) =>
        processValues(vTail, qTail :+ qHead.setRight(vRight))
      case (qHead :: qTail, None :: None :: vTail) =>
        processValues(vTail, qTail)
    }
  }
}
object TreeNode {
  final case class Empty[T]() extends TreeNode[T]
  final case class Branch[T](value: T, left: TreeNode[T], right: TreeNode[T]) extends TreeNode[T]

  def deserialize[T](values: Seq[Option[T]]): TreeNode[T] = {
    values match {
      case Some(headVal) :: tail =>
        val root: MutableTreeNode.Branch[T] = MutableTreeNode.Branch(headVal)
        MutableTreeNode.processValues(tail, Seq(root))
        root.toImmutable()
      case Nil => Empty()
      case _ => throw new RuntimeException("Invalid argument values")
    }
  }
}

object TreeNodeTest extends App {
  val input = Seq(Some(5), Some(4), Some(7), None, None, Some(2), None)
  val treeNode:TreeNode[Int] = TreeNode.deserialize(input)
  println(treeNode)
}

Answer 3

As has been noted, Scala avoids null whenever possible, preferring Option to indicate the absence of a value.

Mutable variables are also shunned, which makes it much easier to construct a B-tree in a depth-first manner rather than breadth-first.

So all you really need is an easy-to-use breadth-first-serialization --to--> depth-first-serialization translator.

I did it in two steps.

//from Breadth-First-Serialization to full tree representation
def BFS2full[A](bfs:IndexedSeq[Option[A]]) :List[List[Option[A]]] = {
  val bfsLen = bfs.length
  if (bfs.isEmpty) Nil
  else
    List(bfs.head) :: List.unfold((List(bfs.head),1)){case (pr,idx) =>
      Option.when(bfsLen > idx){
        val ns = pr.foldLeft((List.empty[Option[A]],idx)){
          case ((acc,x), None) => (acc ++ List(None,None), x)
          case ((acc,x), _) => (acc ++ List(bfs.lift(x).flatten
                                           ,bfs.lift(x+1).flatten), x+2)
        }
        (ns._1, ns)
      }
    }
}

//from full tree representation to Depth-First-Serialization
def toDFS[A](lloa :List[List[Option[A]]]
            ,lvl :Int = 0) :List[Option[A]] = lloa match {
  case Nil => List(None, None)
  case List(None) :: Nil => List(None)
  case List( oa ) :: tl  => oa :: toDFS(tl, lvl)
  case row :: tl => row.drop(lvl*2) match {
    case List(None,None,_*) => List(None, None)
    case List(None, ob ,_*) => None :: (ob::toDFS(tl,2*lvl + 1))
    case List( oa ,None,_*) => (oa::toDFS(tl,2*lvl)) ++ List(None)
    case List( oa , ob ,_*) => (oa :: toDFS(tl, 2*lvl)) ++
                                (ob :: toDFS(tl,2*lvl + 1))
  }
}

Now let's parameterize the tree so that we can build Int trees, Float trees, String trees, etc.

We're also going to make the constructor private so that node creation is only done via factory methods.

case class Tree[A] private (value : A
                           ,left  : Option[Tree[A]]
                           ,right : Option[Tree[A]])

All that's left is to supply the factory methods.

object Tree {
  private def BFS2full[A]( . . . //as above 
  private def toDFS[A]( . . . //as above

  def fromDFS[A](dfs :IterableOnce[Option[A]]) :Option[Tree[A]] = {
    val itr = dfs.iterator
    def loop(): Option[Tree[A]] =
      Option.when(itr.hasNext)(itr.next())
            .flatten
            .map(new Tree(_,loop(),loop()))
    loop()
  }
  def fromBFS[A](bfs:IndexedSeq[Option[A]]) :Option[Tree[A]] =
    fromDFS(toDFS(BFS2full(bfs)))
}

testing:

Tree.fromBFS(Vector(Some('A'),None,Some('B'),Some('C'))).get
//res0: Tree[Char] = Tree(A,None,Some(Tree(B,Some(Tree(C,None,None)),None)))

Answer 4

Here's a basic solution. It doesn't use lazy vals or any data structures other than List, Option, and Either. You might find it easier to understand because of that or harder because of the verbosity.

I've defined Tree like this, just to make things easier.

sealed trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object Empty extends Tree[Nothing]

Also, instead of an Array[Int], I'm using a List[Option[T]] (where T is a type parameter of the makeTree method). Some means there's a node, None is like -1 in your code. This is more idiomatic and also works for types other than Int.

---

The thing about doing this breadth-first is that you need to kinda keep passing the input list around to the children. First you try to make the left child, then when that's done, you try make the right child. Then you try to make the left child's children, then the right child's children, then their children, and so on.

One way to deal this without using var would be to take in the input list containing the serialized binary tree and see what the head of the list is. If it's a None, we can just return an Empty, because we know it's the end of the tree. If it's a Some however, we can't yet return a tree, but we can return another function that takes in the next round of input and returns a tree.

Since there are 2 different types that can be returned, these functions will be of type List[Option[T]] => Either[List[Option[T]] => ThisFunctionsType, Tree[T]]. Since the function may return another function of the same type, we'll have to define a new type that can return itself:

trait RecFun[T] extends ((List[Option[T]]) => (List[Option[T]], Either[RecFun[T], Tree[T]]))

The reason that it's List[Option[T]] => (List[Option[T]], Either[RecFun[T], Tree[T]]) and not just List[Option[T]] => Either[RecFun[T], Tree[T]] is that in case one child turns out to be a leaf somewhere in the middle of the list, we still need to continue, so the first element of the returned tuple contains the rest of the list after processing.

Now we can define this. The helper function is so that as long as the RecFun returns a Left[RecFun], it keeps passing the remaining input into that function.

def makeTree[T](list: List[Option[T]]): Tree[T] = {
  def helper(f: RecFun[T], l: List[Option[T]]): Tree[T] =
    f(l) match {
      case (_, Right(tree)) => tree
      case (next, Left(f))  => helper(f, next)
    }

  list match {
    case Some(x) :: tail => helper(createRec(x), tail)
    case _               => Empty
  }
}

def createRec[T](data: T): RecFun[T] = {
  case None :: Nil | Nil => (Nil, Right(Node(data, Empty, Empty)))
  case Some(l) :: Nil => (Nil, Right(Node(data, Node(l, Empty, Empty), Empty)))
  case lo :: ro :: rest =>
    (rest, (lo, ro) match {
      case (Some(l), Some(r)) =>
        Left(waitForChildren(data, createRec(l), createRec(r)))
      case (Some(l), None) =>
        Left(waitForChild(Node(data, _, Empty), createRec(l)))
      case (None, Some(r)) =>
        Left(waitForChild(Node(data, Empty, _), createRec(r)))
      case (None, None) => Right(Node(data, Empty, Empty))
    })
  }

def waitForChildren[T](data: T, leftF: RecFun[T], rightF: RecFun[T]): RecFun[T] =
  input => {
    val (next, res) = leftF(input)
    res match {
      case Right(tree) =>
        (next, Left(waitForChild(Node(data, tree, _), rightF)))
      case Left(leftF2) => {
        val (next2, res2) = rightF(next)
        (next2, Left(res2 match {
          case Right(tree)   => waitForChild(Node(data, _, tree), leftF2)
          case Left(rightF2) => waitForChildren(data, leftF2, rightF2)
        }))
      }
    }
  }

def waitForChild[T](ctor: Tree[T] => Node[T], f: RecFun[T]): RecFun[T] =
  input => {
    val (next, res) = f(input)
    (next, res match {
      case Right(tree)  => Right(ctor(tree))
      case Left(recFun) => Left(waitForChild(ctor, recFun))
    })
  }

Scastie