Check if two trees are Mirror

Last Updated : 28 Dec, 2023

Given two Binary Trees, write a function that returns true if two trees are mirror of each other, else false. For example, the function should return true for following input trees.

MirrorTree1

Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

This problem is different from the problem discussed here.
For two trees ‘a’ and ‘b’ to be mirror images, the following three conditions must be true:

Their root node’s key must be same
Left subtree of root of ‘a’ and right subtree root of ‘b’ are mirror.
Right subtree of ‘a’ and left subtree of ‘b’ are mirror.

Below is implementation of above idea.

C++

// C++ program to check if two trees are mirror
// of each other
#include<bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to
   left child and a pointer to right child */
struct Node
{
    int data;
    Node* left, *right;
};
 
/* Given two trees, return true if they are
   mirror of each other */
/*As function has to return bool value instead integer value*/
bool areMirror(Node* a, Node* b)
{
    /* Base case : Both empty */
    if (a==NULL && b==NULL)
        return true;
 
    // If only one is empty
    if (a==NULL || b == NULL)
        return false;
 
    /* Both non-empty, compare them recursively
     Note that in recursive calls, we pass left
     of one tree and right of other tree */
    return  a->data == b->data &&
            areMirror(a->left, b->right) &&
            areMirror(a->right, b->left);
}
 
/* Helper function that allocates a new node */
Node* newNode(int data)
{
    Node* node = new Node;
    node->data  = data;
    node->left  =  node->right  = NULL;
    return(node);
}
 
/* Driver program to test areMirror() */
int main()
{
    Node *a = newNode(1);
    Node *b = newNode(1);
    a->left = newNode(2);
    a->right = newNode(3);
    a->left->left  = newNode(4);
    a->left->right = newNode(5);
 
    b->left = newNode(3);
    b->right = newNode(2);
    b->right->left = newNode(5);
    b->right->right = newNode(4);
 
    areMirror(a, b)? cout << "Yes" : cout << "No";
 
    return 0;
}

Java

// Java program to see if two trees 
// are mirror of each other
 
// A binary tree node
class Node 
{
    int data;
    Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
class BinaryTree 
{
    Node a, b;
     
    /* Given two trees, return true if they are
       mirror of each other */
    boolean areMirror(Node a, Node b) 
    {
        /* Base case : Both empty */
        if (a == null && b == null)
            return true;
 
        // If only one is empty
        if (a == null || b == null) 
            return false;
 
        /* Both non-empty, compare them recursively
           Note that in recursive calls, we pass left
           of one tree and right of other tree */
        return a.data == b.data
                && areMirror(a.left, b.right)
                && areMirror(a.right, b.left);
    }
 
    // Driver code to test above methods
    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        Node a = new Node(1);
        Node b = new Node(1);
        a.left = new Node(2);
        a.right = new Node(3);
        a.left.left = new Node(4);
        a.left.right = new Node(5);
 
        b.left = new Node(3);
        b.right = new Node(2);
        b.right.left = new Node(5);
        b.right.right = new Node(4);
 
        if (tree.areMirror(a, b) == true)
            System.out.println("Yes");
        else
            System.out.println("No");
 
    }
}
 
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python3 program to check if two
# trees are mirror of each other
 
# A binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Given two trees, return true 
# if they are mirror of each other
def areMirror(a, b):
     
    # Base case : Both empty
    if a is None and b is None:
        return True
     
    # If only one is empty
    if a is None or b is None:
        return False
     
    # Both non-empty, compare them 
    # recursively. Note that in 
    # recursive calls, we pass left
    # of one tree and right of other tree
    return (a.data == b.data and
            areMirror(a.left, b.right) and
            areMirror(a.right , b.left))
 
# Driver code
root1 = Node(1)
root2 = Node(1)
 
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.left.right = Node(5)
 
root2.left = Node(3)
root2.right = Node(2)
root2.right.left = Node(5)
root2.right.right = Node(4)
 
if areMirror(root1, root2):
    print ("Yes")
else:
    print ("No")
 
# This code is contributed by AshishR

C#

using System;
 
// c# program to see if two trees 
// are mirror of each other 
 
// A binary tree node 
public class Node
{
    public int data;
    public Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
public class BinaryTree
{
    public Node a, b;
 
    /* Given two trees, return true if they are 
    mirror of each other */
    public virtual bool areMirror(Node a, Node b)
    {
        /* Base case : Both empty */
        if (a == null && b == null)
        {
            return true;
        }
 
        // If only one is empty 
        if (a == null || b == null)
        {
            return false;
        }
 
        /* Both non-empty, compare them recursively 
        Note that in recursive calls, we pass left 
        of one tree and right of other tree */
        return a.data == b.data && areMirror(a.left, b.right) 
                            && areMirror(a.right, b.left);
    }
 
    // Driver code to test above methods 
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        Node a = new Node(1);
        Node b = new Node(1);
        a.left = new Node(2);
        a.right = new Node(3);
        a.left.left = new Node(4);
        a.left.right = new Node(5);
 
        b.left = new Node(3);
        b.right = new Node(2);
        b.right.left = new Node(5);
        b.right.right = new Node(4);
 
        if (tree.areMirror(a, b) == true)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
 
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
// javascript program to see if two trees 
// are mirror of each other
 
// A binary tree node
class Node {
     
     Node(data) {
        this.data = data;
        this.left = this.right = null;
    }
}
 
var a, b;
 
    /*
     * Given two trees, return true if they are mirror of each other
     */
    function areMirror( a,  b) {
        /* Base case : Both empty */
        if (a == null && b == null)
            return true;
 
        // If only one is empty
        if (a == null || b == null)
            return false;
 
        /*
         * Both non-empty, compare them recursively Note that in recursive calls, we
         * pass left of one tree and right of other tree
         */
        return a.data == b.data && areMirror(a.left, b.right) && areMirror(a.right, b.left);
    }
 
    // Driver code to test above methods
     
     
         a = new Node(1);
         b = new Node(1);
        left = new Node(2);
        right = new Node(3);
        left.left = new Node(4);
        left.right = new Node(5);
 
        left = new Node(3);
        right = new Node(2);
        right.left = new Node(5);
        right.right = new Node(4);
 
        if (areMirror(a, b) == true)
            document.write("Yes");
        else
            document.write("No");
 
// This code contributed by umadevi9616 
</script>

Output

Yes

Time Complexity: O(n)
Auxiliary Space: O(h) where h is height of binary tree

Approach 2: Iterative Solution

Another approach to check if two trees are mirrors of each other is to use an iterative algorithm that uses a stack to keep track of the nodes being traversed. This algorithm is similar to the iterative algorithm for checking if a tree is symmetric, but with a slight modification to check for mirror symmetry.

This solution uses two stacks to iterate over the two trees in a synchronized way. It pops a node from both stacks, checks if their data is equal, and then pushes their left and right children onto the stacks in the opposite order. The algorithm terminates early if at any point the nodes being compared have unequal data or unequal numbers of children.

Here is the implementation for the iterative solution:

C++

#include <bits/stdc++.h>
using namespace std;
 
// A binary tree node
class Node {
public:
    int data;
    Node* left;
    Node* right;
 
    Node(int d)
    {
        this->data = d;
        this->left = NULL;
        this->right = NULL;
    }
};
 
bool isMirrorIterative(Node* root1, Node* root2)
{
    if (root1 == NULL && root2 == NULL)
        return true;
     
    if (root1 == NULL || root2 == NULL)
        return false;
     
    stack<Node*> s1, s2;
    s1.push(root1);
    s2.push(root2);
     
    while (!s1.empty() && !s2.empty())
    {
        Node* curr1 = s1.top();
        s1.pop();
        Node* curr2 = s2.top();
        s2.pop();
         
        if (curr1->data != curr2->data)
            return false;
         
        if (curr1->left != NULL && curr2->right != NULL)
        {
            s1.push(curr1->left);
            s2.push(curr2->right);
        }
        else if (curr1->left != NULL || curr2->right != NULL)
            return false;
         
        if (curr1->right != NULL && curr2->left != NULL)
        {
            s1.push(curr1->right);
            s2.push(curr2->left);
        }
        else if (curr1->right != NULL || curr2->left != NULL)
            return false;
    }
     
    if (!s1.empty() || !s2.empty())
        return false;
     
    return true;
}
 
int main()
{
    // create the two trees
    Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);
 
    Node* root2 = new Node(1);
    root2->left = new Node(3);
    root2->right = new Node(2);
    root2->right->left = new Node(5);
    root2->right->right = new Node(4);
     
    // check if the two trees are mirrors
    if (isMirrorIterative(root1, root2))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
     
    return 0;
}

Java

import java.util.*;
 
// A binary tree node
class Node {
int data;
Node left;
Node right;
  Node(int d) {
    this.data = d;
    this.left = null;
    this.right = null;
}
}
 
class Main {
static boolean isMirrorIterative(Node root1, Node root2) {
if (root1 == null && root2 == null)
return true;
      if (root1 == null || root2 == null)
        return false;
 
    Stack<Node> s1 = new Stack<>();
    Stack<Node> s2 = new Stack<>();
    s1.push(root1);
    s2.push(root2);
 
    while (!s1.empty() && !s2.empty()) {
        Node curr1 = s1.pop();
        Node curr2 = s2.pop();
 
        if (curr1.data != curr2.data)
            return false;
 
        if (curr1.left != null && curr2.right != null) {
            s1.push(curr1.left);
            s2.push(curr2.right);
        } else if (curr1.left != null || curr2.right != null)
            return false;
 
        if (curr1.right != null && curr2.left != null) {
            s1.push(curr1.right);
            s2.push(curr2.left);
        } else if (curr1.right != null || curr2.left != null)
            return false;
    }
 
    if (!s1.empty() || !s2.empty())
        return false;
 
    return true;
}
 
public static void main(String[] args) {
    // create the two trees
    Node root1 = new Node(1);
    root1.left = new Node(2);
    root1.right = new Node(3);
    root1.left.left = new Node(4);
    root1.left.right = new Node(5);
 
    Node root2 = new Node(1);
    root2.left = new Node(3);
    root2.right = new Node(2);
    root2.right.left = new Node(5);
    root2.right.right = new Node(4);
 
    // check if the two trees are mirrors
    if (isMirrorIterative(root1, root2))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}

Python3

# Python program for the above approach
class Node:
    def __init__(self, d):
        self.data = d
        self.left = None
        self.right = None
 
# Function to check if two binary trees are mirrors of each other
def isMirrorIterative(root1, root2):
    # If both trees are empty, they are mirrors
    if root1 is None and root2 is None:
        return True
 
    # If one tree is empty and the other is not, they are not mirrors
    if root1 is None or root2 is None:
        return False
 
    stack1 = []
    stack2 = []
    stack1.append(root1)
    stack2.append(root2)
 
    while len(stack1) > 0 and len(stack2) > 0:
        curr1 = stack1.pop()
        curr2 = stack2.pop()
 
        # If data of current nodes doesn't match, they are not mirrors
        if curr1.data != curr2.data:
            return False
 
        # Check the left child of first tree and the right child of the second tree
        if curr1.left is not None and curr2.right is not None:
            stack1.append(curr1.left)
            stack2.append(curr2.right)
        elif curr1.left is not None or curr2.right is not None:
            return False
 
        # Check the right child of first tree and the left child of the second tree
        if curr1.right is not None and curr2.left is not None:
            stack1.append(curr1.right)
            stack2.append(curr2.left)
        elif curr1.right is not None or curr2.left is not None:
            return False
 
    # If any stack is not empty, trees are not mirrors
    if len(stack1) > 0 or len(stack2) > 0:
        return False
 
    # Trees are mirrors
    return True
 
# create the two trees
root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.left.right = Node(5)
 
root2 = Node(1)
root2.left = Node(3)
root2.right = Node(2)
root2.right.left = Node(5)
root2.right.right = Node(4)
 
# check if the two trees are mirrors
if isMirrorIterative(root1, root2):
    print("Yes")  # Output: Yes
else:
    print("No")   # Output: No

C#

using System;
using System.Collections.Generic;
 
// Definition for a binary tree node
class Node
{
    public int Data;
    public Node Left, Right;
 
    public Node(int data)
    {
        Data = data;
        Left = Right = null;
    }
}
 
class Solution
{
    /*
     * Function to check if two binary trees are mirrors of each other iteratively
     * Returns true if trees are mirrors, false otherwise
     */
    public bool IsMirrorIterative(Node root1, Node root2)
    {
        // If both trees are empty, they are mirrors
        if (root1 == null && root2 == null)
            return true;
 
        // If one tree is empty and the other is not, they are not mirrors
        if (root1 == null || root2 == null)
            return false;
 
        // Create two stacks for iterative traversal of trees
        Stack<Node> stack1 = new Stack<Node>();
        Stack<Node> stack2 = new Stack<Node>();
        stack1.Push(root1);
        stack2.Push(root2);
 
        // Iterative traversal using stacks
        while (stack1.Count > 0 && stack2.Count > 0)
        {
            Node curr1 = stack1.Pop();
            Node curr2 = stack2.Pop();
 
            // If data of current nodes doesn't match, they are not mirrors
            if (curr1.Data != curr2.Data)
                return false;
 
            // Check the left child of the first tree and the right child of the second tree
            if (curr1.Left != null && curr2.Right != null)
            {
                stack1.Push(curr1.Left);
                stack2.Push(curr2.Right);
            }
            else if (curr1.Left != null || curr2.Right != null)
                return false;
 
            // Check the right child of the first tree and the left child of the second tree
            if (curr1.Right != null && curr2.Left != null)
            {
                stack1.Push(curr1.Right);
                stack2.Push(curr2.Left);
            }
            else if (curr1.Right != null || curr2.Left != null)
                return false;
        }
 
        // If any stack is not empty, trees are not mirrors
        if (stack1.Count > 0 || stack2.Count > 0)
            return false;
 
        // Trees are mirrors
        return true;
    }
}
 
class Program
{
    static void Main()
    {
        // Create the two trees
        Node root1 = new Node(1);
        root1.Left = new Node(2);
        root1.Right = new Node(3);
        root1.Left.Left = new Node(4);
        root1.Left.Right = new Node(5);
 
        Node root2 = new Node(1);
        root2.Left = new Node(3);
        root2.Right = new Node(2);
        root2.Right.Left = new Node(5);
        root2.Right.Right = new Node(4);
 
        // Instantiate the Solution class
        Solution solution = new Solution();
 
        // Check if the two trees are mirrors
        if (solution.IsMirrorIterative(root1, root2))
            Console.WriteLine("Yes"); // Output: Yes
        else
            Console.WriteLine("No"); // Output: No
    }
}

Javascript

// JavaScript Program for the above approach
class Node {
  constructor(d) {
    this.data = d;
    this.left = null;
    this.right = null;
  }
}
 
// Function to check if two binary trees are mirrors of each other
function isMirrorIterative(root1, root2) {
  // If both trees are empty, they are mirrors
  if (root1 === null && root2 === null)
    return true;
 
  // If one tree is empty and the other is not, they are not mirrors
  if (root1 === null || root2 === null)
    return false;
 
  const stack1 = [];
  const stack2 = [];
  stack1.push(root1);
  stack2.push(root2);
 
  while (stack1.length > 0 && stack2.length > 0) {
    const curr1 = stack1.pop();
    const curr2 = stack2.pop();
 
    // If data of current nodes doesn't match, they are not mirrors
    if (curr1.data !== curr2.data)
      return false;
 
    // Check the left child of first tree and the right child of the second tree
    if (curr1.left !== null && curr2.right !== null) {
      stack1.push(curr1.left);
      stack2.push(curr2.right);
    } else if (curr1.left !== null || curr2.right !== null)
      return false;
 
    // Check the right child of first tree and the left child of the second tree
    if (curr1.right !== null && curr2.left !== null) {
      stack1.push(curr1.right);
      stack2.push(curr2.left);
    } else if (curr1.right !== null || curr2.left !== null)
      return false;
  }
 
  // If any stack is not empty, trees are not mirrors
  if (stack1.length > 0 || stack2.length > 0)
    return false;
 
  // Trees are mirrors
  return true;
}
 
// create the two trees
const root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);
 
const root2 = new Node(1);
root2.left = new Node(3);
root2.right = new Node(2);
root2.right.left = new Node(5);
root2.right.right = new Node(4);
 
// check if the two trees are mirrors
if (isMirrorIterative(root1, root2))
  console.log("Yes"); // Output: Yes
else
  console.log("No"); // Output: No
 
// THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL

Output

Yes

Time Complexity: O(n)
Auxiliary Space: O(h) where h is height of binary tree

Iterative method to check if two trees are mirror of each other

A

Ashish Gupta

Improve

Previous Article

Check if a Binary Tree contains duplicate subtrees of size 2 or more

Foldable Binary Trees

Similar Reads

Check if a number is prime in Flipped Upside Down, Mirror Flipped and Mirror Flipped Upside Down

Given an integer N, the task is to check if N is a prime number in Flipped Down, Mirror Flipped and Mirror Flipped Down forms of the given number.Examples: Input: N = 120121 Output: YesExplanation: Flipped forms of the number:Flipped Upside Down - 151051Mirror Flipped - 121021Mirror Upside Down - 150151Since 1510151 and 121021 are both prime number

Check if two trees are mirror of each other using level order traversal

Given two binary trees, the task is to check whether the two binary trees is a mirror of each other or not.Mirror of a Binary Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Trees in the above figure are mirrors of each other. A recursive solution and an iterative method u

Check if two binary trees are mirror | Set 3

Given two arrays, A[] and B[] consisting of M pairs, representing the edges of the two binary trees of N distinct nodes according to the level order traversal, the task is to check if trees are the mirror images of each other. Examples: Input: N = 6, M = 5, A[][2] = {{1, 5}, {1, 4}, {5, 7}, {5, 8}, {4, 9}}, B[][2] = {{1, 4}, {1, 5}, {4, 9}, {5, 8},

Iterative method to check if two trees are mirror of each other

Given two binary trees. The problem is to check whether the two binary trees are mirrors of each other or not. Mirror of a Binary Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Trees in the above figure are mirrors of each other. Recommended PracticeTwo Mirror TreesTry It

Check if two trees are Mirror | Set 2

Given two Binary Trees, returns true if two trees are mirror of each other, else false. Mirror Tree : Previously discussed approach is here. Approach: Find the inorder traversal of both the Binary Trees, and check whether one traversal is reverse of another or not. If they are reverse of each other then the trees are mirror of each other, else not.

Check if given Trees can be made mirror images of each other in K swaps

Given two binary tree with same structure but may have different arrangement of value and given an integer K. The task is to check that after exactly K swap on first tree, will it become mirror of second one. In one swap we take two node of same parent and swap its left and right subtree. Examples: Input: K = 1 1 1 / \ / \ 2 3 2 3Output: Yes Input:

Check if the given two matrices are mirror images of one another

Given two matrices mat1[][] and mat2[][] of size NxN. The task is to find if the given two matrices are mirror images of one another. Print “Yes” if the given two matrices are mirror images, otherwise print “No”. Two matrices mat1 and mat2 of size N*N are said to be mirror images of one another if for any valid index (i, j) of the matrix: mat1[i][j

Introduction to Generic Trees (N-ary Trees)

Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes. Every node stores address of its children and the very first node's address will be stored in a s

Total number of possible Binary Search Trees and Binary Trees with n keys

Total number of possible Binary Search Trees with n different keys (countBST(n)) = Catalan number Cn = (2n)! / ((n + 1)! * n!) For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, .... So are numbers of Binary Search Trees. Total number of possible Binary Trees with n different keys (countBT(n)) = countBST(n

Check if the given string is the same as its reflection in a mirror

Given a string S containing only uppercase English characters. The task is to find whether S is the same as its reflection in a mirror.Examples: Input: str = "AMA" Output: YES AMA is same as its reflection in the mirror. Input: str = "ZXZ" Output: NO Approach: The string obviously has to be a palindrome, but that alone is not enough. All characters

Article Tags :

Practice Tags :