Symmetric Tree

Easy Problem 66 of 151 Java and Python

Practice on LeetCode

Problem

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

Example 1

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

Example 2

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

Constraints

1 ≤ number of nodes ≤ 1000

Explanation

The tree is symmetric when the left subtree is the mirror image of the right subtree.

Two trees a and b are mirrors when their roots match, a.left mirrors b.right, and a.right mirrors b.left. It is Same Tree with the children crossed over.

Approach 1 · Naive

Compare level by level

Time O(n)
Space O(w)

Read each level from left to right, including null placeholders, and check that it reads the same backwards.

BFS level by level, recording values (null as a marker) for every child slot.
Each level's list must be a palindrome.

Java

import java.util.*;

class Solution {
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> level = new ArrayList<>();
        level.add(root);
        while (!level.isEmpty()) {
            for (int i = 0, j = level.size() - 1; i < j; i++, j--) {
                TreeNode a = level.get(i);
                TreeNode b = level.get(j);
                if (a == null || b == null ? a != b : a.val != b.val) {
                    return false;
                }
            }
            List<TreeNode> next = new ArrayList<>();
            for (TreeNode node : level) {
                if (node != null) {
                    next.add(node.left);
                    next.add(node.right);
                }
            }
            level = next;
        }
        return true;
    }
}

Python

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        level = [root]
        while level:
            values = [node.val if node else None for node in level]
            if values != values[::-1]:
                return False
            level = [child for node in level if node for child in (node.left, node.right)]
        return True

Approach 2 · Optimal

Recursive mirror check

Time O(n)
Space O(h)

Check that the left and right subtrees are mirrors, comparing outer pairs and inner pairs.

mirror(a, b): if either is null, return whether both are.
Return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left).
Answer is mirror(root.left, root.right).

Java

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return mirror(root.left, root.right);
    }

    private boolean mirror(TreeNode a, TreeNode b) {
        if (a == null || b == null) {
            return a == b;
        }
        return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
    }
}

Python

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(a, b):
            if not a or not b:
                return a is b
            return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)

        return mirror(root.left, root.right)

Complexity compared

Approach	Time	Space
Naive Compare level by level	O(n)	O(w)
Optimal Recursive mirror check	O(n)	O(h)

Key takeaways

Recognise the shared pattern with Same Tree: one helper over a pair of nodes.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem