Notebook

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Source

In [1]:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Code

In [2]:

def is_symmetric(root):
    """Simplest solution using recursion.
    Tree is symetric if left subtree (p) is the mirror of RIGHT subtree (q)
            i.e.    p.val = q.val
            AND     p.left = q.right
            AND     p.right = q.left
    Time Complexity: O(n)
    Space Complexity: O(n).
    """
    def is_mirror(left, right):
        if not left or not right:
            return left == right
        return (left.val == right.val
                and is_mirror(left.left, right.right)
                and is_mirror(left.right, right.left))

    return is_mirror(root, root)

Follow up:

Solve it both recursively and iteratively.

Code

In [3]:

def is_symmetric(root):
    """Iterative approach.
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    if not root:
        return True
    stack = [(root.left, root.right)]
    while stack:
        left, right = stack.pop()
        if left is None and right is None:
            continue
        if left is None or right is None:
            return False
        if left.val != right.val:
            return False
        stack.append((left.left, right.right))
        stack.append((left.right, right.left))
    return True