Symmetric Tree
Mahabharata — The Balanced Vyuha — Is the Formation a Perfect Mirror?
बायां और दायां — दर्पण में एक दूसरे?। बाहर से अंदर — जांचो हर जोड़ी॥
*Left and right — mirrors of each other? Check outer to inner — every pair.*
The Story
Check if a binary tree is symmetric around its center.
For `[1,2,2,3,4,4,3]`: true (symmetric). For `[1,2,2,null,3,null,3]`: false.
**Mirror check:** ```java public boolean isSymmetric(TreeNode root) { return root == null || mirror(root.left, root.right); }
boolean mirror(TreeNode left, TreeNode right) { if (left == null && right == null) return true; // Both null if (left == null || right == null) return false; // Only one null return left.val == right.val && mirror(left.left, right.right) // Outer pair && mirror(left.right, right.left); // Inner pair } ```
The key: `mirror(left, right)` checks if left and right subtrees are mirror images of each other. - Outer pair: left.left mirrors right.right - Inner pair: left.right mirrors right.left
Trace `[1,2,2,3,4,4,3]`: - mirror(2,2): 2==2 && mirror(3,3) && mirror(4,4) - mirror(3,3): 3==3 && mirror(null,null) && mirror(null,null) → true - mirror(4,4): same → true - All true → symmetric ✓
Trace `[1,2,2,null,3,null,3]`: - mirror(2,2): 2==2 && mirror(null,null) && mirror(3,3)? Wait: - left=2: left.left=null, left.right=3 - right=2: right.left=null, right.right=3 - mirror(left.left=null, right.right=3): one null → false!
The Level-Order Mirror Check
Collect each level. Check if level array is palindrome. Edge case: null nodes must match in mirror positions. O(n).
// Recursive IS optimal. No simpler brute force.
// The mirror() recursive approach is the standard solution.The Outer-Inner Mirror Recursion
public boolean isSymmetric(TreeNode root) {
return root == null || mirror(root.left, root.right);
}
boolean mirror(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
return left.val == right.val
&& mirror(left.left, right.right)
&& mirror(left.right, right.left);
}Step-by-Step Walkthrough
Tree=[1]: root.left=null, root.right=null. mirror(null,null)=true. isSymmetric=true ✅ Tree=[1,2,2]: mirror(2,2): 2==2 && mirror(null,null) && mirror(null,null) → true ✅
Deep Insight
**Symmetric vs Invert:** tr-7 (Invert) modifies the tree. tr-8 (Symmetric) just checks. The mirror() function compares two subtrees — conceptually it checks if one subtree equals the inverted form of the other.
**Iterative queue version:** ```java Queue<TreeNode> q = new LinkedList<>(); q.offer(root.left); q.offer(root.right); while (!q.isEmpty()) { TreeNode l=q.poll(), r=q.poll(); if (l==null && r==null) continue; if (l==null || r==null || l.val!=r.val) return false; q.offer(l.left); q.offer(r.right); // Outer q.offer(l.right); q.offer(r.left); // Inner } return true; ``` Pairs are processed together: always enqueue outer pair and inner pair together.
**tr-9 (Same Tree) is similar:** mirror(l, r) checks if l is a mirror of r. isSameTree(p, q) checks if p equals q structurally.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(h) | Recursive call stack = height |
| Optimal | O(n) | O(h) | Each pair of nodes visited once |
Pattern Recognition
✅ Symmetric tree = left mirrors right ✅ mirror(l,r): outer pair + inner pair cross-check ✅ mirror(l.left, r.right) AND mirror(l.right, r.left) ✅ Iterative: enqueue pairs (outer, inner) together **LeetCode Trigger Phrases:** → "symmetric tree" → Is tree a mirror image → Compare two subtrees as mirror images
Bhagavad Gita 6.29
सर्वभूतस्थमात्मानं सर्वभूतानि चात्मनि। ईक्षते योगयुक्तात्मा सर्वत्र समदर्शनः॥
With a mind united in yoga and seeing the Self in all beings and all beings in the Self — the yogi sees sameness everywhere.
Connection: A symmetric tree sees itself equally from all angles — the left is the perfect mirror of the right. Like the yogi who sees the same divine Self in all beings and all beings in the Self (samadarsana), the symmetric tree contains perfect symmetry — each node on the left has its exact counterpart on the right. The mirror() function verifies this by checking each mirroring pair, confirming the same divine pattern repeating symmetrically.