Symmetric Tree

Intuition

Symmetry is a property that relates two subtrees rather than a single node, so the natural helper takes two nodes and asks whether one is the mirror of the other. Two nodes are mirrors when both are null, or when their values match and their children mirror in a crossed fashion. The crossing is the key insight: the left child of one must mirror the right child of the other, and vice versa. Starting the helper on the root's two children answers the whole question. Every reachable pair is examined once, giving a linear traversal.

Algorithm walkthrough

1. 1Handle the empty tree: a null root is trivially symmetric, return true.
2. 2Call a helper isMirror(left, right) on the root's two children.
3. 3In the helper, if both nodes are null the pair mirrors, return true.
4. 4If exactly one is null, or their values differ, the pair fails, return false.
5. 5Recurse on the crossed pairs: left.left vs right.right, and left.right vs right.left.
6. 6The tree is symmetric only when both crossed comparisons succeed.

Implementation

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isMirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            if left is None and right is None:
                return True
            if left is None or right is None or left.val != right.val:
                return False
            return isMirror(left.left, right.right) and isMirror(left.right, right.left)

        if root is None:
            return True
        return isMirror(root.left, root.right)