Check if 2 trees are mirror or not

Problem Statement

Given two binary trees, check if they are mirrors of each other. Two trees are mirrors if the left subtree of one is identical to the right subtree of the other, and vice versa.

Example 1:

Example 2:

Approach 1: Brute Force (Create Mirror and Compare)

Intuition

Create the mirror of one tree, then check if it's identical to the other tree. This requires two passes - one to create mirror, one to compare.

Algorithm

1. Create a mirror of Tree 1 (swap left and right children at each node)
2. Check if the mirrored Tree 1 is identical to Tree 2
3. Return the comparison result

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode createMirror(TreeNode root) {
        if (root == null) return null;
        
        TreeNode newNode = new TreeNode(root.val);
        newNode.left = createMirror(root.right);
        newNode.right = createMirror(root.left);
        
        return newNode;
    }
    
    private boolean areIdentical(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        
        return t1.val == t2.val &&
               areIdentical(t1.left, t2.left) &&
               areIdentical(t1.right, t2.right);
    }
    
    public boolean areMirrorBruteForce(TreeNode root1, TreeNode root2) {
        // Create mirror of root1
        TreeNode mirror1 = createMirror(root1);
        
        // Check if mirror equals root2
        return areIdentical(mirror1, root2);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Create mirror O(n) + compare O(n)
• Space Complexity: O(n) - Extra space to store the mirror tree

Approach 2: Optimal (Direct Mirror Check)

Intuition

Instead of creating a mirror and comparing, directly check if two trees are mirrors by comparing left of one with right of other, and vice versa. This avoids creating extra tree.

Algorithm

1. If both roots are null, they're mirrors (base case)
2. If one is null and other isn't, not mirrors
3. Check if values are equal
4. Recursively check: left1 with right2, and right1 with left2
5. Both conditions must be true

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public boolean areMirror(TreeNode root1, TreeNode root2) {
        // Both empty - mirrors
        if (root1 == null && root2 == null) {
            return true;
        }
        
        // One empty, one not - not mirrors
        if (root1 == null || root2 == null) {
            return false;
        }
        
        // Check current values and cross-compare subtrees
        return root1.val == root2.val &&
               areMirror(root1.left, root2.right) &&
               areMirror(root1.right, root2.left);
    }
}

Iterative Approach Using Queue

Complexity Analysis

• Time Complexity: O(n) - Each node is visited once
• Space Complexity: O(h) - Recursion stack depth, where h is height of tree

Key Takeaways

1. Mirror property: left1 ↔ right2 and right1 ↔ left2
2. Direct comparison avoids creating extra tree structure
3. Cross-comparison is the key insight - compare opposite children
4. This is related to checking if a single tree is symmetric (mirror of itself)
5. Both recursive and iterative solutions work with same time complexity