Sunday, December 21, 2008

99 problems - python - 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.

# Example in Haskell:

# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
# False
# *Main> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
# True

def mirror(tree):
if tree == None:
return None
val, left, right = tree
return (None, mirror(right), mirror(left))

def symmetric_binary_tree(tree):
return mirror(mirror(tree)) == mirror(tree)

No comments: