101. Symmetric Tree

Reformulated question¶

Given a binary tree root, return True if its left and right subtrees are mirror images of each other.

Example:

[1,2,2,3,4,4,3] -> True
because:
left  = 2(3,4)
right = 2(4,3)

Key trick¶

Compare nodes in pairs that must mirror each other:

a.val == b.val
a.left mirrors b.right
a.right mirrors b.left

Trap¶

Comparing only values per level is not enough.
Ignoring None positions gives false positives.
Accessing root.left when root is None is unsafe outside LeetCode-style assumptions.

Why is this question interesting?¶

It tests whether you see tree symmetry as a two-pointer problem on trees:

left side walks outward one way
right side walks outward the opposite way

Solve the problem with idiomatic python¶

from utils import TreeNode
from typing import Optional

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
            # both missing: symmetric here
            if a is None and b is None:
                return True

            # exactly one missing or different values: not symmetric
            if a is None or b is None or a.val != b.val:
                return False

            # outer children must match, and inner children must match
            return mirror(a.left, b.right) and mirror(a.right, b.left)

        return True if root is None else mirror(root.left, root.right)

This is the standard direct solution.
Time is \(O(n)\) and recursion stack is \(O(h)\).

Pytest test¶

from utils import tree_build
from typing import Optional
import pytest

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([1], True),
        ([1, 2, 2], True),
        ([1, 2, 2, 3, 4, 4, 3], True),
        ([1, 2, 2, None, 3, None, 3], False),
        ([1, 2, 2, None, 3, 3, None], True),
        ([1, 2, 2, 3, None, None, 3], True),
        ([1, 2, 2, 3, None, 3, None], False),
        ([1, 2, 3], False),
    ],
)
def test_is_symmetric(values, expected):
    root = tree_build(values)
    assert Solution().isSymmetric(root) is expected

Comment my solution¶

Your solution works much harder than needed.

The path-tracking idea is unnecessary.
Symmetry is local and recursive, so storing full paths adds avoidable complexity.
It does not represent missing children explicitly, which is the usual bug source in level-based approaches.
if root.left is None and root.right is None: assumes root exists.
The helper is_sym_node checks path complementarity, but mirror recursion already encodes that more simply and safely.

A simpler and more interview-friendly version is the recursive mirror check above.

from utils import TreeNode, tree_build
from typing import Optional
import pytest
from collections import deque

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # The number of nodes in the tree is in the range `[1, 1000]`.
        if root.left is None and root.right is None:
            return True
        if not (root.left and root.right):
            return False
        def is_sym_node(node_path1, node_path2):
            n1, p1 = node_path1
            n2, p2 = node_path2
            if n1.val != n2.val:
                return False
            if len(p1) != len(p2):
                return False
            for i in range(len(p1)):
                if p1[i] ^ p2[i] == 0:
                    return False
            return True
        # (node, path) where path is array of [0,1,0,1] 0 for left, 1 for right
        # nodes are symmetric if path1 symmetric of path2
        nodes_same_level = [(root.left, [0]), (root.right, [1])]
        while nodes_same_level:
            if len(nodes_same_level) % 2 != 0:
                return False
            next_level_left = []
            next_level_right = deque([])
            left_idx, right_idx = 0, len(nodes_same_level) - 1
            while left_idx < right_idx:
                left = nodes_same_level[left_idx]
                right = nodes_same_level[right_idx]

                if not is_sym_node(left, right):
                    return False

                left_node, left_path = left[0], left[1]
                if left_node.left:
                    next_level_left.append((left_node.left, left_path + [0]))
                if left_node.right:
                    next_level_left.append((left_node.right, left_path + [1]))

                right_node, right_path = right[0], right[1]
                if right_node.right:
                    next_level_right.appendleft((right_node.right, right_path + [1]))
                if right_node.left:
                    next_level_right.appendleft((right_node.left, right_path + [0]))

                left_idx += 1
                right_idx -= 1
            nodes_same_level = next_level_left + list(next_level_right)

        return True

class SolutionRecursive:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # Implemented after reading comments from AI
        def is_sym_level(level):
            if not any(level):
                return True
            n = len(level)
            next_level = []
            for i in range(n):
                if i < (n // 2):
                    n1 = level[i].val if level[i] else None
                    n2 = level[n - 1 - i].val if level[n - 1 - i] else None
                    if n1 != n2:
                        return False

                next_left = None if level[i] is None else level[i].left
                next_right = None if level[i] is None else level[i].right
                next_level.append(next_left)
                next_level.append(next_right)
            return is_sym_level(next_level)
        return is_sym_level([root])


@pytest.mark.parametrize(
    ("values", "is_symmetric"),
    [
        ([1], True),
        ([1,2,2,3,4,4,3], True),
        ([1,2,2,None,3,None,3], False),
        ([1,2,3], False)
    ],
)
def test_isSymmetric(values, is_symmetric):
    root = tree_build(values)
    assert Solution().isSymmetric(root) == is_symmetric
    assert SolutionRecursive().isSymmetric(root) == is_symmetric