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 ...Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
