SymmetricTree

Problem

https://leetcode.com/problems/symmetric-tree/

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 1000].

• -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

Solution

Starting at the root, observe that it does not affect the symmetry of the tree. Only the left and right subtrees with roots left = root.left and right = root.right do. We need to check if the left subtree is a mirror image of the right. This is true if and only if left.val == right.val and the subtree of``left.left`` is a mirror image of right.right and the subtree of left.right is a mirror image of right.left. Checking whether the further subtrees are mirror images of each other can be solved using recursion, until both children are null.

                     root
           /                    \\
        left-                   right-
    /         \\             /          \\
left.left+ left.right* right.left+ right.right*

The - nodes should be equal in value, while the + subtrees, and * subtrees should be mirror images.

Pattern

Tree, Depth-First Search, Breadth-First Search, Binary Tree

Code

class TreeNode:
    """Node in a binary tree.
    """

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def isSymmetric(root: TreeNode | None) -> bool:
    """Returns whether a binary tree is symmetric.
    """
    if root is None:
        return True
    else:
        return check_subtrees(root.left, root.right)


def check_subtrees(left: TreeNode | None, right: TreeNode | None) -> bool:
    """Returns whether the left and right subtrees are mirror images of each
    other.
    """
    if left is right is None:
        return True
    elif left is None and right is not None:
        return False
    elif left is not None and right is None:
        return False
    elif left.val != right.val:
        return False
    else:
        return check_subtrees(left.left, right.right) and check_subtrees(left.right, right.left)

Test

>>> from SymmetricTree import TreeNode, isSymmetric
>>> root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
>>> isSymmetric(root)
True
>>> root = TreeNode(1, TreeNode(2, None, TreeNode(2)), TreeNode(2, None, TreeNode(2)))
>>> isSymmetric(root)
False

class SymmetricTree.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

SymmetricTree.check_subtrees(left: TreeNode | None, right: TreeNode | None) → bool

Returns whether the left and right subtrees are mirror images of each other.

SymmetricTree.isSymmetric(root: TreeNode | None) → bool

Returns whether a binary tree is symmetric.