Is Tree Symmetric

Problem name: isTreeSymmetric

Problem description is here.

#
# Definition for binary tree:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
def isTreeSymmetric(t):
    if t is None or (t.left is None and t.right is None):
        return True
    
    if t.left is None and t.right is not None:
        return False
    if t.left is not None and t.right is None:
        return False
    
    left_cursor = t.left
    right_cursor = t.right
    return isEqual(left_cursor, right_cursor)
    
def isEqual(left, right):
    # value 
    # shape
    if left is None or right is None:
        return left is None and right is None
    return left.value == right.value and isEqual(left.left, right.right) and isEqual(left.right, right.left) 

Time Complexity

O(N) # N is the length of BinaryTree

Solving Strategy

The symmetric condition means that left subtree of root node is the mirror image of the right subtree of root node.

Then, we can recursively decide this tree is symmetric using two conditions, left node of left subtree is same as right node of right subtree, and right node of left subtree is same as left node of right subtree. If one node is empty, which is None, then the mirror image of the node is also empty. Furthermore, the value of two nodes also need to same.

Since all condition is concatenate using and operator, one condition is false, final result is false, which means that the tree is not symmetric.