Comparing trees

How do we compare two trees to know whether they are equal or not? Note that the trees could have the same values but could differ structurally.

The diagram shows two complete binary trees. However, as shown, these two are not equal.

To check this, we need to traverse both the trees at the same time. How could we perform this traversal? Of course, we do this using a tuple match:

  scala>   def equal[A](tree1: BinTree[A], tree2: BinTree[A]): Boolean = (tree1, 
     |     tree2) match { 
     |     case (Leaf, Leaf) => true 
     |     case (Branch(v1, l1, r1), Branch(v2, l2, r2)) if v1 == v2 => 
     |       equal(l1, l2) && equal(r1, r2) 
     |     case _ => false 
     |   } 
scala>  val tree1 = buildTree(List(1,2,3,4,5,6,7)) 
tree1: BinTree.BinTree[Int] = Branch(1,Branch(2,Branch(3,Leaf,Leaf),Branch(4,Leaf,Leaf)),Branch(5,Branch(6,Leaf,Leaf),Branch(7,Leaf,Leaf))) 
 
scala>  val tree2 = buildTree(List(1,2,3,4,5,7,6)) 
tree2: BinTree.BinTree[Int...