medium Mirror Image Trees

Problem Statement

Given two binary trees root and root2, return true if they are mirror images of each other. Otherwise, return false.

Two trees are said to be mirror images if, for every node in one tree, there is a corresponding node in the other tree with a mirrored structure. This means the left subtree of one tree is a mirror reflection of the right subtree of the other tree, and vice versa.

Examples

Example 1

• Input: root1 = [1,2,3,4,null,null,5], root2 = [1,3,2,5,null,null,4]

• Expected Output: true
• Justification: Both trees have the same root, and the left and right subtrees are mirrors of each other.

Example 2

• Input: root1 = [4, 5, 6, null, 7], root2 = [4, 6, 5, null, null, 7]

• Expected Output: true
• Justification: Both trees are a mirror of each other.

Example 3

• Input: root1 = [1, 2, null, 3], root2 = [1, null, 2]

• Expected Output: false
• Justification: The structure of the subtrees differs. The first tree contains node 3 but the second tree doesn't.

Solution

To solve this problem, we will use the Breadth-First Search (BFS) approach, which allows us to traverse both binary trees level by level. We maintain two queues to compare the nodes of both trees at each level in a mirrored manner. We add the left child of the first tree and the right child of the second tree to their respective queues, and vice versa. This way, the algorithm checks for symmetry at every level. If at any point, we find that the node values or their structures differ, we return false. If both queues are empty at the end of traversal, the trees are mirrors, and we return true.

The BFS approach is well-suited for this problem because it ensures that we process all nodes in a controlled manner. By utilizing two queues, we can efficiently compare nodes without recursion, which prevents stack overflow issues for deep trees. This method ensures that both trees are checked for symmetry in a straightforward, iterative manner, making it both effective and space-efficient.

Step-by-Step Algorithm

1. Initial Check:

   • If both trees are empty (root1 == null and root2 == null), return true since two empty trees are considered mirrors.
   • If one tree is empty while the other is not, return false, as they cannot be mirrors.

2. Queue Initialization:

   • Initialize two queues: queue1 and queue2.
   • Enqueue the root of the first tree into queue1 and the root of the second tree into queue2.

3. Traversal Loop:

   • While both queues are not empty:
     • Dequeue the front of both queues (node1 from queue1 and node2 from queue2).
     • Value Check:
       • If the value of node1 is not equal to node2, return false.
     • Left and Right Child Check:
       • For the left child of node1 and the right child of node2:
         • If both are not null, enqueue node1.left to queue1 and node2.right to queue2.
         • If one is null and the other is not, return false.
       • For the right child of node1 and the left child of node2:
         • If both are not null, enqueue node1.right to queue1 and node2.left to queue2.
         • If one is null and the other is not, return false.

4. Completion:

   • After the traversal loop, check if both queues are empty.
   • If both are empty, return true (the trees are mirrors). Otherwise, return false.

Algorithm Walkthrough

Input: root1 = [1,2,3,4,null,null,5], root2 = [1,3,2,5,null,null,4]

1. Initial Check:

   • Both root1 and root2 are not null, so we proceed.

2. Queue Initialization:

   • Enqueue root1 (value 1) into queue1.
   • Enqueue root2 (value 1) into queue2.

3. First Iteration:

   • Dequeue queue1 → node1 = 1.
   • Dequeue queue2 → node2 = 1.
   • Value Check: node1.val == node2.val (1 == 1), so continue.
   • Left and Right Child Check:
     • node1.left = 2 and node2.right = 2: Both are not null, so enqueue 2 to queue1 and 2 to queue2.
     • node1.right = 3 and node2.left = 3: Both are not null, so enqueue 3 to queue1 and 3 to queue2.

4. Second Iteration:

   • Dequeue queue1 → node1 = 2.
   • Dequeue queue2 → node2 = 2.
   • Value Check: node1.val == node2.val (2 == 2), so continue.
   • Left and Right Child Check:
     • node1.left = 4 and node2.right = 4: Both are not null, so enqueue 4 to queue1 and 4 to queue2.
     • node1.right = null and node2.left = null: Both are null, so continue.

5. Third Iteration:

   • Dequeue queue1 → node1 = 3.
   • Dequeue queue2 → node2 = 3.
   • Value Check: node1.val == node2.val (3 == 3), so continue.
   • Left and Right Child Check:
     • node1.left = null and node2.right = null: Both are null, so continue.
     • node1.right = 5 and node2.left = 5: Both are not null, so enqueue 5 to queue1 and 5 to queue2.

6. Fourth Iteration:

   • Dequeue queue1 → node1 = 4.
   • Dequeue queue2 → node2 = 4.
   • Value Check: node1.val == node2.val (4 == 4), so continue.
   • Left and Right Child Check:
     • node1.left = null and node2.right = null: Both are null, so continue.
     • node1.right = null and node2.left = null: Both are null, so continue.

7. Fifth Iteration:

   • Dequeue queue1 → node1 = 5.
   • Dequeue queue2 → node2 = 5.
   • Value Check: node1.val == node2.val (5 == 5), so continue.
   • Left and Right Child Check:
     • node1.left = null and node2.right = null: Both are null, so continue.
     • node1.right = null and node2.left = null: Both are null, so continue.

8. Completion:

   • Both queue1 and queue2 are now empty, meaning the trees are mirror images. Return true.

Code

import java.util.LinkedList;
import java.util.Queue;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
    
//     TreeNode(int val) {
//         this.val = val;
//         left = null;
//         right = null;
//     }
// }

public class Solution {

    public boolean areMirrors(TreeNode root1, TreeNode root2) {
        // If both roots are null, they are mirrors
        if (root1 == null && root2 == null) return true;
        // If one is null and the other is not, they are not mirrors
        if (root1 == null || root2 == null) return false;

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        
        // Start by adding both roots to their respective queues
        queue1.add(root1);
        queue2.add(root2);
        
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            // Poll the front of each queue
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            
            // Check if the values are different
            if (node1.val != node2.val) return false;
            
            // Add children in mirror order
            // Add left child of root1 and right child of root2 to queues
            if (node1.left != null && node2.right != null) {
                queue1.add(node1.left);
                queue2.add(node2.right);
            } else if (!(node1.left == null && node2.right == null)) {
                return false; // One child is null, the other is not
            }

            // Add right child of root1 and left child of root2 to queues
            if (node1.right != null && node2.left != null) {
                queue1.add(node1.right);
                queue2.add(node2.left);
            } else if (!(node1.right == null && node2.left == null)) {
                return false; // One child is null, the other is not
            }
        }
        
        return queue1.isEmpty() && queue2.isEmpty();
    }
    
    public static void main(String[] args) {
        // Creating first tree root1 = [1,2,3,4,null,null,5]
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.right.right = new TreeNode(5);

        // Creating second tree root2 = [1,3,2,5,null,null,4]
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(3);
        root2.right = new TreeNode(2);
        root2.left.left = new TreeNode(5);
        root2.right.right = new TreeNode(4);
        
        // Create instance of Solution to call areMirrors method
        Solution solution = new Solution();
        
        // Test the trees and print the result
        boolean result = solution.areMirrors(root1, root2);
        System.out.println("Are the two trees mirror images? " + result); // Expected output: true
    }
}

Complexity Analysis

Time Complexity

• In the worst-case scenario, both trees will have n nodes (where n is the number of nodes in either tree).
• During the BFS traversal, every node in both trees is visited exactly once. For each node, we perform constant-time operations (checking if values match, enqueueing children, etc.).
• Hence, the overall time complexity is , where n is the number of nodes in the trees.

Space Complexity

• The space complexity is determined by the maximum size of the queue. In the worst-case scenario, both trees are balanced, and the queue can hold at most nodes at a given time (since we are storing nodes of both trees in queues).
• Therefore, the space complexity is .