LeetCode · #101

Symmetric Tree Solution

Check whether the left and right subtrees are mirror images of each other.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #101

🏗️

Pattern

Tree DFS — mirror recursion

Return true if a binary tree is symmetric around its center. That means the left subtree must be the mirror image of the right subtree.

Example

 Input: [1,2,2,3,4,4,3]
Output: true // left.right must match right.left, and left.left must match right.right 

Section Two · Approach 1

Serialize and Compare — O(n)

One idea is to serialize the left subtree and compare it to a mirrored serialization of the right subtree.

Problem: This works, but it is indirect and easy to get wrong unless null markers are handled perfectly. A direct mirror recursion is cleaner and more natural.

Section Three · Approach 2

Recursive Mirror Check — O(n)

Define a helper isMirror(a, b) that checks whether two subtrees mirror each other.

💡 Mental model: Fold the tree down the vertical middle. Matching nodes must land on top of each other. So the outside pair compares to the outside pair, and the inside pair compares to the inside pair.

Mirror rules

If both nodes are null → they match.
If exactly one is null → not symmetric.
If values differ → not symmetric.
Otherwise compare a.left with b.right and a.right with b.left.

Key insight:

This is not a normal “same tree” comparison.
The cross-pairs matter: left-left compares with right-right, and left-right compares with right-left.

Section Four · Trace

Visual Walkthrough

Mirror comparisons happen in cross order

Section Five · Implementation

Code — Java & Python

Java — recursive mirror check

 class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.left, root.right);
    }
private boolean isMirror(TreeNode a, TreeNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
if (a.val != b.val) return false;
return isMirror(a.left, b.right)
            && isMirror(a.right, b.left);
    }
}

Python — recursive mirror check

 class Solution:
def isSymmetric(self, root) -> bool:
def mirror(a, b):
if not a and not b:
return True if not a or not b:
return False if a.val != b.val:
return False return mirror(a.left, b.right) and mirror(a.right, b.left)
if not root:
return True return mirror(root.left, root.right)

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Serialize + compare	O(n)	O(n)
Recursive mirror DFS	O(n)	O(h)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Why it matters
Empty tree	An empty tree is symmetric by definition.
Single node	Also symmetric — both subtrees are null.
Same values, wrong shape	Structure must mirror too, not just values.

⚠ Common Mistake: Comparing a.left with b.left and a.right with b.right. That checks whether the subtrees are identical, not mirrored.

← Back to Trees problems

LearningTree

LC 101 · Symmetric Tree — Solution & Explanation | DSA Guide