Print binary tree in multiline format

script.scala

// Print binary tree on multiple lines maintaining dependency of parent-children
//  0|            1 
//  1|      7          8 
//  2|   4     5   *      9 
//  3| *  *  *  *       5   * 
//  4|                *  * 

abstract class TreeNode
case class NIL() extends TreeNode
case class BinaryTreeNode(
    value: Int,
    left: TreeNode = NIL(),
    right: TreeNode = NIL()) extends TreeNode {
  def isLeaf: Boolean = left == NIL() && right == NIL()
}

def height(root: TreeNode): Int = root match {
  case a: BinaryTreeNode => 1 + math.max(height(a.left), height(a.right))
  case b: NIL => 1
}

def traverse(buf: Array[String], node: TreeNode, level: Int): Int = {
  node match {
    case b: BinaryTreeNode =>
      val left = traverse(buf, b.left, level + 1)
      val right = traverse(buf, b.right, level + 1)
      val mid = (left + right + 1) / 2
      if (buf(level).length < mid) {
        buf(level) += " " * (mid - buf(level).length)
      }
      val prevLen = buf(level).length
      buf(level) += s" ${b.value} "
      prevLen
    case c: NIL =>
      val len = buf.map(_.length).max
      if (buf(level).length < len) {
        buf(level) += " " * (len - buf(level).length)
      }
      val prevLen = buf(level).length
      buf(level) += " * "
      prevLen
  }
}

def tree(root: TreeNode): Array[String] = {
  val buf = (0 until height(root)).map { x =>
    s"${x.toString.reverse.padTo(3, " ").reverse.mkString}|"
  }.toArray
  traverse(buf, root, 0)
  buf
}

val root = BinaryTreeNode(1,
  BinaryTreeNode(7,
    BinaryTreeNode(4),
    BinaryTreeNode(5)
  ),
  BinaryTreeNode(8,
    BinaryTreeNode(5,
      BinaryTreeNode(4),
      BinaryTreeNode(9)
    ),
    BinaryTreeNode(9,
      BinaryTreeNode(2),
      BinaryTreeNode(8,
        BinaryTreeNode(5,
          BinaryTreeNode(4),
          BinaryTreeNode(9)
        )
      )
    )
  )
)
tree(root).foreach(println)
/*
scala> tree(root).foreach(println)
  0|                1
  1|      7                   8
  2|   4     5        5               9
  3| *  *  *  *    4     9     2            8
  4|             *  *  *  *  *  *       5      *
  5|                                 4     9
  6|                               *  *  *  *
*/

val root = BinaryTreeNode(1,
  NIL(),
  BinaryTreeNode(8,
    BinaryTreeNode(5,
      BinaryTreeNode(4),
      BinaryTreeNode(9)
    ),
    BinaryTreeNode(9,
      BinaryTreeNode(2)
    )
  )
)
tree(root).foreach(println)
/*
scala> tree(root).foreach(println)
  0|        1
  1| *             8
  2|         5          9
  3|      4     9     2   *
  4|    *  *  *  *  *  *
*/