Code for checking the symmetry of a binary tree doesn't work as expected

Question

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

It's easy to find a solution that works, but I was wondering why my solution doesn't work. The way I tried doing this is the following: first reflect the original tree about the vertical axis passing through the root, and then compare the reflected tree with the original tree. The reflected tree is equal to the original tree iff the original tree is symmetric.

My code is below. It breaks, for example for the input root = [1,2,2,null,3,null,3] -- the output is True instead of False. But I don't see why this is happening; the two internal functions work as intended I believe.

# 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

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
            if root is None:
                return None
            root.left, root.right = invertTree(root.right), invertTree(root.left)

            return root

        def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
            if p is None and q is None:
                return True
            elif p is not None and q is None:
                return False
            elif p is None and q is not None:
                return False
            elif p.val != q.val: 
                return False

            return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

        inverted_root = invertTree(root)

        return isSameTree(root, inverted_root)

Answer 1

A quick fix would be:

root_copy = copy.deepcopy(root)
inverted_root = invertTree(root)
return isSameTree(root_copy, inverted_root)

Answer 2

Your invertTree function does not create a new tree, but mutates the given tree. There is only one root, but you just got a new reference to it with inverted_root. Comparing root with inverted_root is comparing the (mutated) tree with itself and will always return True.

You can still use the idea of the inplace mutation of the tree, but apply it only on the right subtree, and then check whether the (non modified) left subtree is the same as the (mutated) right subtree.

To do that, replace these statements:

        inverted_root = invertTree(root)
        return isSameTree(root, inverted_root)

with:

        inverted_right = invertTree(root.right)
        return isSameTree(root.left, inverted_right)

NB: it is given in the code challenge that the tree has at least one node, so root will not be None.