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

From HaskellWiki
Jump to: navigation, search
 
m (Remove special case from 'symmetric')
Line 10: Line 10:
 
symmetric Empty = True
 
symmetric Empty = True
 
symmetric (Branch _ l r) = mirror l r
 
symmetric (Branch _ l r) = mirror l r
  +
</haskell>
  +
  +
Even simpler is
  +
<haskell>
  +
symmetric t = mirror t t
 
</haskell>
 
</haskell>

Revision as of 17:15, 3 May 2014

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