Tree.scala

import scala.annotation.tailrec

sealed trait Tree[+A] {
  def isSymmetric: Boolean
}

object Tree {
  final case class Node[+A](left: Tree[A], value: A, right: Tree[A]) extends Tree[A] {
    def isSymmetric: Boolean = {
      @tailrec def loop(
          queue1: List[Tree[A]],
          queue2: List[Tree[A]],
          frontier1: List[Tree[A]],
          frontier2: List[Tree[A]]
      ): Boolean = (queue1, queue2, frontier1, frontier2) match {
        case (Nil, Nil, Nil, Nil) => true
        case (Nil, Nil, frontier1, frontier2) =>
          loop(frontier1, frontier2, Nil, Nil)
        case (Leaf :: queue1, Leaf :: queue2, frontier1, frontier2) =>
          loop(queue1, queue2, frontier1, frontier2)
        case (Node(left1, value1, right1) :: queue1, Node(left2, value2, right2) :: queue2, frontier1, frontier2)
            if value1 == value2 =>
          loop(queue1, queue2, left1 :: right1 :: frontier1, right2 :: left2 :: frontier2)
        case _ => false
      }

      loop(left :: Nil, right :: Nil, Nil, Nil)
    }
  }

  case object Leaf extends Tree[Nothing] {
    def isSymmetric: Boolean = true
  }
}

object Test extends App {
  import Tree._

  println(Node(Node(Node(Leaf, 2, Leaf), 1, Leaf), 0, Node(Leaf, 1, Node(Leaf, 2, Leaf))).isSymmetric)
}