gistfile1.txt

case class BinaryTree(left: BinaryTree, right: BinaryTree)

def isComplete(tree: BinaryTree): Boolean = {
  val q = scala.collection.mutable.Queue(tree)
  var expectNull = false
  while(!q.isEmpty) {
    val n = q.dequeue
    if (n != null) {
      if (expectNull) {
        return false
      } else {
        q.enqueue(n.left)
        q.enqueue(n.right)
      }
    } else
      expectNull = true
  }
  true
}

scala> isComplete(BinaryTree(null, null))
res3: Boolean = true

scala> isComplete(BinaryTree(null, BinaryTree(null, null)))
res4: Boolean = false

scala> isComplete(BinaryTree(BinaryTree(null, null), BinaryTree(null, null)))
res5: Boolean = true

scala> isComplete(BinaryTree(BinaryTree(null, null), BinaryTree(BinaryTree(null, null), null)))
res6: Boolean = false

scala> isComplete(BinaryTree(BinaryTree(BinaryTree(null, null), null), BinaryTree(null, null)))
res7: Boolean = true

scala> isComplete(BinaryTree(BinaryTree(BinaryTree(null, null), null), BinaryTree(BinaryTree(null, null), null)))
res8: Boolean = false

scala> isComplete(BinaryTree(BinaryTree(BinaryTree(null, null), BinaryTree(null, null)), BinaryTree(BinaryTree(null, null), null)))
res9: Boolean = true

scala> isComplete(BinaryTree(BinaryTree(BinaryTree(null, null), BinaryTree(null, null)), BinaryTree(null, BinaryTree(null, null))))
res10: Boolean = false