EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Symmetric Tree

1 approach, code in every language

Given the root of a binary tree, decide whether the tree is a mirror image of itself around its center. In other words, check whether the left subtree is the reflection of the right subtree.

A tree is symmetric when reflecting it left-to-right produces an identical shape and identical values. This is different from the two subtrees merely being equal; the comparison must be done in mirrored order.

Example 1

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

Output: true

The left subtree [2,3,4] mirrors the right subtree [2,4,3]: matching outer children (3 vs 3) and matching inner children (4 vs 4).

Example 2

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

Output: false

Both children of the root are 2, but a mirror requires the left node's right child (3) to match the right node's left child, which is null. One side has the node and the other is missing it, so the mirror alignment breaks.

Constraints

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

Recursive Mirror Comparison

Compare two nodes at a time, matching each node's outer child with the other's outer child.

Loading animation…

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

1Handle the empty tree: a null root is trivially symmetric, return true.
2Call a helper isMirror(left, right) on the root's two children.
3In the helper, if both nodes are null the pair mirrors, return true.
4If exactly one is null, or their values differ, the pair fails, return false.
5Recurse on the crossed pairs: left.left vs right.right, and left.right vs right.left.
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)

Time

O(n)

Space

O(h)

Every node participates in at most one mirror comparison, so the work is linear. The recursion depth is bounded by the tree height h.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Chime Hangs True is our own problem on the technique behind Symmetric Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free