A TCO version of binary tree symmetry checker

tree-check.scala

package treechecker
import scala.annotation.tailrec


sealed trait Tree
case class Branch[A](a: A, left: Tree, right: Tree) extends Tree
case object Leaf extends Tree


object TreeChecker {
  def symmetrical(t: Tree): Boolean = t match {
    case Branch(_, l, r) => symmetrical(l -> r)
    case Leaf => true
  }


  @tailrec
  def symmetrical(tp: (Tree, Tree), tpl: List[(Tree, Tree)] = Nil): Boolean = tp match {
    case (Branch(l, ll, lr), Branch(r, rl, rr)) => if(l != r) false else symmetrical(ll -> rl, lr -> rr :: tpl)
    case (Leaf, Leaf) => tpl match {
      case h :: t => symmetrical(h, t)
      case _ => true }
    case (_, _) => false
  }
}