99 questions/Solutions/56

(**) Symmetric binary trees

Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes.

mirror Empty          Empty          = True
mirror (Branch _ a b) (Branch _ x y) = mirror a y && mirror b x
mirror _              _              = False

symmetric Empty          = True
symmetric (Branch _ l r) = mirror l r

Even simpler is

symmetric t = mirror t t

It could be misunderstood that an equality checker just ignoring the branch name may solve the issue. However, this does not consider the cases where two immediate branches may not be the same, but the tree as a whole could be symmetric. Hence a mirror function is more encompassing. We need a symmetry - not equality.