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