LeetCode 101: Symmetric Tree

Problem Restatement

We are given the root of a binary tree.

We need to check whether the tree is symmetric around its center. In other words, the left subtree must be a mirror image of the right subtree. The official problem asks whether the binary tree is a mirror of itself.

A tree like this is symmetric:

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

The left side and right side have the same shape, but reversed.

A tree like this is not symmetric:

        1
      /   \
     2     2
      \     \
       3     3

Both sides contain 3, but their positions do not mirror each other.

Input and Output

LeetCode gives the TreeNode class:

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

The function shape is:

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        ...

Examples

Consider this tree:

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

The root value is 1.

The left child and right child both have value 2.

Now compare their children as mirrors:

left.left   should match   right.right
left.right  should match   right.left

So we compare:

3 with 3
4 with 4

Everything matches, so the answer is:

True

Now consider this tree:

        1
      /   \
     2     2
      \     \
       3     3

At first, the two 2 nodes match.

But the left subtree has 3 as a right child, while the right subtree also has 3 as a right child.

For symmetry, the right subtree should have 3 as a left child.

So the answer is:

False

First Thought: Compare the Two Sides

A symmetric tree has a simple rule:

The left subtree and the right subtree must be mirror images.

That means we should not compare:

left.left with right.left
left.right with right.right

That would check whether both subtrees are identical.

Instead, we compare across the center:

left.left with right.right
left.right with right.left

This is the core idea.

Key Insight

We can define a helper function:

mirror(a, b)

This function answers one question:

“Are the two trees rooted at a and b mirrors of each other?”

For two nodes to be mirrors:

1. Both nodes are missing, so they match.
2. One node is missing and the other exists, so they do not match.
3. Both nodes exist, but their values differ, so they do not match.
4. Both nodes exist with the same value, so their children must mirror across the center.

The recursive mirror check is:

a.left  mirrors b.right
a.right mirrors b.left

Algorithm

Start from the root.

If the tree is empty, return True.

Otherwise, compare the root’s left child with the root’s right child.

For each pair of nodes:

1. If both nodes are None, return True.
2. If only one node is None, return False.
3. If the values are different, return False.
4. Recursively compare the outside pair.
5. Recursively compare the inside pair.
6. Return True only if both recursive checks are true.

Correctness

The helper function mirror(a, b) checks exactly the definition of mirror symmetry.

If both nodes are missing, the two empty subtrees are mirrors.

If one node is missing and the other exists, the shape differs, so the subtrees cannot be mirrors.

If both nodes exist but their values differ, the subtrees cannot be mirrors because matching mirrored positions must contain the same value.

If both nodes exist and have the same value, the remaining condition is structural. The outside children must mirror each other, and the inside children must mirror each other:

a.left  with b.right
a.right with b.left

The recursion applies the same rule at every lower level of the tree.

The full tree is symmetric exactly when root.left and root.right are mirrors. Therefore, the algorithm returns True exactly for symmetric trees.

Complexity

Here, n is the number of nodes and h is the height of the tree.

For a balanced tree, h = O(log n).

For a completely skewed tree, h = O(n).

Implementation

from typing import Optional

# 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 mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
            if a is None and b is None:
                return True

            if a is None or b is None:
                return False

            if a.val != b.val:
                return False

            return mirror(a.left, b.right) and mirror(a.right, b.left)

        return mirror(root.left, root.right)

Code Explanation

The helper function compares two nodes at mirrored positions:

def mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:

If both are missing, they match:

if a is None and b is None:
    return True

If only one is missing, the shape is different:

if a is None or b is None:
    return False

If both exist but have different values, symmetry fails:

if a.val != b.val:
    return False

Then we compare the mirrored children:

return mirror(a.left, b.right) and mirror(a.right, b.left)

The outer pair is a.left and b.right.

The inner pair is a.right and b.left.

Finally, the whole tree is symmetric when the left and right children of the root mirror each other:

return mirror(root.left, root.right)

Testing

For local testing, we can define a small TreeNode class and build trees manually.

from typing import Optional

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 mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
            if a is None and b is None:
                return True

            if a is None or b is None:
                return False

            if a.val != b.val:
                return False

            return mirror(a.left, b.right) and mirror(a.right, b.left)

        return mirror(root.left, root.right)

def run_tests():
    s = Solution()

    root1 = TreeNode(
        1,
        TreeNode(2, TreeNode(3), TreeNode(4)),
        TreeNode(2, TreeNode(4), TreeNode(3)),
    )
    assert s.isSymmetric(root1) is True

    root2 = TreeNode(
        1,
        TreeNode(2, None, TreeNode(3)),
        TreeNode(2, None, TreeNode(3)),
    )
    assert s.isSymmetric(root2) is False

    root3 = TreeNode(1)
    assert s.isSymmetric(root3) is True

    root4 = TreeNode(
        1,
        TreeNode(2),
        TreeNode(3),
    )
    assert s.isSymmetric(root4) is False

    root5 = TreeNode(
        1,
        TreeNode(2, TreeNode(3), None),
        TreeNode(2, None, TreeNode(3)),
    )
    assert s.isSymmetric(root5) is True

    print("all tests passed")

run_tests()

Test meaning: