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.

Comparing trees

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 ...

Get Learning Functional Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.