Binary Search Tree from Sorted Array

Given a sorted array, write an algorithm to create a binary search tree with minimal height

Scala

import scala.collection.mutable

trait BTree

object Empty extends BTree

case class Node(var value: Int, var left: BTree = Empty, var right: BTree = Empty) extends BTree

def printBTree(root: BTree): Unit = {
  val queue = mutable.Queue[(BTree, Int)]((root, 0))
  var prev = -1
  while (!queue.isEmpty) {
    val (node, level) = queue.dequeue()
    node match {
      case n: Node => {
        if (level != prev) {
          print("\n#")
          prev = level
        }
        print(n.value)
        queue.enqueue((n.left, level + 1))
        queue.enqueue((n.right, level + 1))
      }
      case _ =>
    }
  }
}

/**
  * 4.3
  *
  * @param arr
  * @return
  */
def buildTree(arr: Array[Int]): BTree = {
  buildTreeRange(arr, 0, arr.length - 1)
}

def buildTreeRange(arr: Array[Int], start: Int, end: Int): BTree = {
  if (arr.length == 0 || end < start) Empty
  else {
    val mid: Int = (end + start) / 2
    val node: Node = Node(arr(mid))
    node.left = buildTreeRange(arr, start, mid - 1)
    node.right = buildTreeRange(arr, mid + 1, end)
    node
  }
}

val root = buildTree(Array(1, 2, 3, 4))
printBTree(root)

Second Tab