# Difference between revisions of "99 questions/Solutions/56"

(categorize) |
|||

(2 intermediate revisions by 2 users not shown) | |||

Line 11: | Line 11: | ||

symmetric (Branch _ l r) = mirror l r |
symmetric (Branch _ l r) = mirror l r |
||

</haskell> |
</haskell> |
||

+ | |||

+ | Even simpler is |
||

+ | <haskell> |
||

+ | symmetric t = mirror t t |
||

+ | </haskell> |
||

+ | |||

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

+ | |||

+ | |||

+ | [[Category:Programming exercise spoilers]] |

## Latest revision as of 13:36, 25 December 2016

(**) 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.