Check if two binary trees are mirror images of each other

Problem

Given two binary trees check if they are mirror image of each other.

Examples

Example 1:

graph LR
	subgraph Original
	A(1) --- B(2) & C(3)
	B --- D(4)
	B ~~~ N1:::hidden
	C ~~~ N2:::hidden
	C --- E(5)
	end

	subgraph Mirror
	A1(1) --- C1(3) & B1(2)
	C1 --- E1(5)
	C1 ~~~ N3:::hidden
	B1 ~~~ N4:::hidden
	B1 --- D1(4)

	end

Original --> Mirror
classDef hidden display:none

Input: root1=[1,2,3,4,null,null,5], root2=[1,3,2,5,null,null,4]
Output: true
Explanation:
Tree 2 is the mirror image of Tree 1.

Example 2:

Input:
 Tree 1:   1
          / \
         2   3
 
 Tree 2:   1
          / \
         2   4
 
Output: false
 
Explanation: The right subtree of Tree 1 (3) is not a mirror of the left subtree of Tree 2 (4).

Solution

Method 1 - Using Preorder

Do the preorder traversal on both the trees simultaneously. if any node doesn’t have corresponding node in the another tree, return false. check if left node in one tree is the right node in another tree, and vice verse.

To check if two binary trees are mirror images:

1. Compare the root nodes of each tree. They must be equal.
2. Recursively check that:
   • The left subtree of the first tree is a mirror to the right subtree of the second tree.
   • The right subtree of the first tree is a mirror to the left subtree of the second tree.

If these conditions hold true for all nodes recursively, the trees are mirror images of each other.

Approach

1. Base Case:
   • If both nodes are null, return true (they are mirrors at this point).
   • If one node is null while the other isn't, return false.
2. Recursive Case:
   • Compare the values of the current nodes of both trees.
   • Recursively check:
     • The left subtree of the first tree is the mirror of the right subtree of the second.
     • The right subtree of the first tree is the mirror of the left subtree of the second.
3. Return the result of recursive checks.

Code

Java

class Solution {
    public boolean areMirrors(TreeNode root1, TreeNode root2) {
        // Base case: Both trees are empty
        if (root1 == null && root2 == null) {
            return true;
        }
        // If one of the trees is empty, they are not mirrors
        if (root1 == null || root2 == null) {
            return false;
        }
        // Check if the current nodes have the same value and their subtrees are mirrors
        return root1.val == root2.val &&
            areMirrors(root1.left, root2.right) &&
            areMirrors(root1.right, root2.left);
    }
}

Python

class Solution:
    def areMirrors(self, root1: TreeNode, root2: TreeNode) -> bool:
        # Base case: Both trees are empty
        if not root1 and not root2:
            return True
        # If one of the trees is empty, they are not mirrors
        if not root1 or not root2:
            return False
        # Check if the current nodes have the same value and their subtrees are mirrors
        return (
            root1.val == root2.val and
            self.areMirrors(root1.left, root2.right) and
            self.areMirrors(root1.right, root2.left)
        )

Complexity

• ⏰ Time complexity: O(n) where n is the number of nodes in the larger of the two trees. We need to visit every node once.
• 🧺 Space complexity: O(h) where h is the height of the larger tree. This is due to the recursive call stack.