Symmetry in a Tree

Problem

Given a binary tree (not necessarily a binary search tree), check if the tree is symmetric. A tree is symmetric if the nodes on the left mirror the nodes on the right. A tree is asymmetric if it is not symmetric.

Input

• tree - A tree node consisting of a value, and left/right children.

Approach

We can approach the solution in two steps:

1. Copy the tree and swap the left and right nodes with each other at each level
2. Compare the original tree and the mirrored tree by traversing down both trees simultaneously.

    def mirrorize_tree(tree):
        if tree is None:
            return

        tree.left, tree.right = tree.right, tree.left
        mirrorize_tree(tree.left)
        mirrorize_tree(tree.right)

The second step is also not too shabby.

    def equals_tree(tree1, tree2):
        if not tree1 and not tree2:
            return True

        if tree1 and tree2 and tree1.data is tree2.data:
            return equals_tree(tree1.left, tree2.left) and equals_tree(tree1.right, tree2.right)

        return False

Now, all we need to do is copy the original tree and mirrorize the tree, then compare the two trees.

    mirror_tree = deepcopy(tree)  # O(n) space for n nodes in the tree
    mirrorize_tree(mirror_tree)  # O(log n)
    return equals_tree(tree, mirror_tree)  #  O(n) time

Optimization

We can save some space complexity by skipping the copying of the original tree.

In a similar light to equals_tree(tree1, tree2), we can examine two trees and check for a couple things that make a tree symmetric.

Cases for symmetry:

• If \(tree1\) and \(tree2\) is both null, then we can say its symmetric because they are equivalent. (See black nodes)
• If the left node of \(tree1\) is the same as the right node of \(tree2\) and the left node of \(tree2\) is the same as the right node of \(tree1\), then we can say its symmetric. (i.e. the two 3 nodes)

All other cases must mean that the original tree is asymmetric because \(tree1\) and \(tree2\) are not mirrored.

def is_symmetric(tree):

    def are_subtrees_symmetric(tree_l, tree_r):
        if not tree_l and not tree_r:
            return True

        if tree_l and tree_r and tree_l.data is tree_r.data:
            return are_subtrees_symmetric(tree_l.left, tree_r.right) and \
                   are_subtrees_symmetric(tree_l.right, tree_r.left)

        return False


    return are_subtrees_symmetric(tree.left, tree.right)