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
