[Easy] 101. Symmetric Tree

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

Thinking Process

1. Mirror Comparison: Compare left subtree with right subtree as mirrors
   • a->left ↔ b->right (outer nodes)
   • a->right ↔ b->left (inner nodes)

• Trees have no cycles — recursion is natural.
• Combine results from left and right subtrees at each node.
• Base case is usually null; height drives stack space.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Examples

Example 1:

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

Tree structure:
      1
     / \
    2   2
   / \ / \
  3  4 4  3

Example 2:

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

Tree structure:
      1
     / \
    2   2
     \   \
      3   3

Constraints

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

Common Mistakes

1. Empty tree: root = [] → return true
2. Single node: root = [1] → return true
3. Symmetric tree: [1,2,2,3,4,4,3] → return true
4. Asymmetric structure: [1,2,2,null,3,null,3] → return false
5. Asymmetric values: [1,2,2,3,4,5,3] → return false

6. One child: [1,2,null] → return false

7. Wrong comparison order: Comparing a->left with b->left instead of b->right

   # WRONG:
   return isMirror(a.left, b.left)  and  isMirror(a.right, b.right);
   # ❌ This checks if trees are identical, not mirrors
   

8. Not handling null correctly: Accessing values before null check
9. Wrong logic operator: Using OR instead of AND
10. Missing value check: Only checking structure, not values
11. Comparing same side: Forgetting to cross-compare (left with right)

Related Problems

• LC 101: Symmetric Tree - This problem
• LC 100: Same Tree - Check if two trees are identical
• LC 226: Invert Binary Tree - Mirror a binary tree
• LC 572: Subtree of Another Tree - Check if subtree exists
• LC 104: Maximum Depth of Binary Tree - Find maximum depth
• LC 110: Balanced Binary Tree - Check if tree is balanced

Key Takeaways

1. Mirror Comparison: Compare left subtree with right subtree as mirrors
2. Cross Comparison:
   • a->left ↔ b->right (outer nodes)
   • a->right ↔ b->left (inner nodes)
3. Three Base Cases: Both null, one null, or value mismatch
4. AND Logic: Both comparisons must succeed for symmetry
5. Empty Tree: Empty tree is symmetric

References

• LC 101: Symmetric Tree on LeetCode
• LeetCode Discuss — LC 101: Symmetric Tree
• LeetCode Editorial (may require premium)

Template Reference

• Trees