Check if two trees are Mirror

Last Updated : 23 Jul, 2025

Given two Binary Trees, the task is to check if two trees are mirror of each other or not. For two trees ‘a’ and ‘b’ to be mirror images, the following three conditions must be true: 

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

Example:

Input:

Two-Mirror-Trees-1

Output: True
Explanation: Both trees are mirror images of each other, so output is True

Input:

Two-Mirror-Trees-2

Output: False
Explanation: Since both trees are not mirror images of each other, the output is False.

Table of Content

[Expected Approach - 1] Recursive Approach - O(n) Time and O(h) Space

The idea is to check if two binary trees are mirrors of each other by comparing their structure and node values. We recursively verify if the root nodes of both trees have the same value, then check if the left subtree is a mirror of the right subtree. If both trees are empty, they are considered mirrors; if one is empty and the other is not, they are not mirrors. This approach ensures that the trees are symmetric with respect to their root.

Below is implementation of above approach:

C++ 
// Recursive C++ program to check if two 
// roots are mirror of each other
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
  
    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

// Function to check if two roots are mirror images
bool areMirrors(Node* root1, Node* root2) {
  
    // If both roots are empty, they are mirrors
    if (root1 == nullptr && root2 == nullptr)
        return true;
    
    // If only one root is empty, they are not mirrors
    if (root1 == nullptr || root2 == nullptr)
        return false;
    
    // Check if the root data is the same and
    // if the left subroot of root1 is a mirror 
    //of the right subroot of root2 and vice versa
    return (root1->data == root2->data) &&
           areMirrors(root1->left, root2->right) &&
           areMirrors(root1->right, root2->left);
}

int main() {
  
    // Representation of input binary tree 1
    //        1
    //       / \
    //      3   2
    //          / \
    //         5   4
    Node* root1 = new Node(1);
    root1->left = new Node(3);
    root1->right = new Node(2);
    root1->right->left = new Node(5);
    root1->right->right = new Node(4);

    // Representation of input binary tree 2 (mirror)
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    Node* root2 = new Node(1);
    root2->left = new Node(2);
    root2->right = new Node(3);
    root2->left->left = new Node(4);
    root2->left->right = new Node(5);

    if (areMirrors(root1, root2))
        cout << "true\n";
    else
        cout << "false\n";

    return 0;
}
C 
// Recursive C program to check if two 
// roots are mirror of each other
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node *left, *right;
};

// Function to check if two roots are mirror images
bool areMirrors(struct Node* root1, 
                  struct Node* root2) {
  
    // If both roots are empty, they are mirrors
    if (root1 == NULL && root2 == NULL)
        return true;
    
    // If only one root is empty, they are not mirrors
    if (root1 == NULL || root2 == NULL)
        return false;
    
    // Check if the root data is the same and
    // if the left subroot of root1 is a mirror 
    // of the right subroot of root2 and vice versa
    return (root1->data == root2->data) &&
           areMirrors(root1->left, root2->right) &&
           areMirrors(root1->right, root2->left);
}

struct Node* createNode(int val) {
    struct Node *newNode 
      = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
  
    // Representation of input binary tree 1
    //        1
    //       / \
    //      3   2
    //          / \
    //         5   4
    struct Node *root1 = createNode(1);
    root1->left = createNode(3);
    root1->right = createNode(2);
    root1->right->left = createNode(5);
    root1->right->right = createNode(4);

    // Representation of input binary tree 2 (mirror)
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    struct Node *root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(3);
    root2->left->left = createNode(4);
    root2->left->right = createNode(5);

    if (areMirrors(root1, root2))
        printf("true\n");
    else
        printf("false\n");

    return 0;
}
Java 
// Recursive Java program to check if two
// roots are mirror images of each other
class Node {
    int data;
    Node left, right;
  
    Node(int val) {
        data = val;
        left = right = null;
    }
}

public class GfG {
    
    // Function to check if two roots are mirror images
    static boolean areMirrors(Node root1, Node root2) {
        
        // If both roots are empty, they are mirrors
        if (root1 == null && root2 == null) {
            return true;
        }
        
        // If only one root is empty, they are not mirrors
        if (root1 == null || root2 == null) {
            return false;
        }
        
        // Check if the root data is the same and
        // if the left subroot of root1 is a mirror 
        // of the right subroot of root2 and vice versa
        return (root1.data == root2.data) &&
               areMirrors(root1.left, root2.right) &&
               areMirrors(root1.right, root2.left);
    }

    public static void main(String[] args) {
        
        // Representation of input binary tree 1
        //        1
        //       / \
        //      3   2
        //          / \
        //         5   4
        Node root1 = new Node(1);
        root1.left = new Node(3);
        root1.right = new Node(2);
        root1.right.left = new Node(5);
        root1.right.right = new Node(4);

        // Representation of input binary tree 2 (mirror)
        //        1
        //       / \
        //      2   3
        //     / \
        //    4   5
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);

        if (areMirrors(root1, root2)) {
            System.out.println("true");
        } 
        else {
            System.out.println("false");
        }
    }
}
Python 
# Recursive Python program to check if two
# roots are mirror images of each other
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

def are_mirrors(root1, root2):
  
    # If both roots are empty, they are mirrors
    if root1 is None and root2 is None:
        return True
    
    # If only one root is empty, they are not mirrors
    if root1 is None or root2 is None:
        return False
    
    # Check if the root data is the same and
    # if the left subroot of root1 is a mirror 
    # of the right subroot of root2 and vice versa
    return (root1.data == root2.data) and \
           are_mirrors(root1.left, root2.right) and \
           are_mirrors(root1.right, root2.left)

if __name__ == "__main__":
  
    # Representation of input binary tree 1
    #        1
    #       / \
    #      3   2
    #          / \
    #         5   4
    root1 = Node(1)
    root1.left = Node(3)
    root1.right = Node(2)
    root1.right.left = Node(5)
    root1.right.right = Node(4)

    # Representation of input binary tree 2 (mirror)
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root2 = Node(1)
    root2.left = Node(2)
    root2.right = Node(3)
    root2.left.left = Node(4)
    root2.left.right = Node(5)

    if are_mirrors(root1, root2):
        print("true")
    else:
        print("false")
C# 
// Recursive C# program to check if two
// roots are mirror images of each other
using System;

class Node {
    public int data;
    public Node left, right;
  
    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class GfG {
  
    // Function to check if two roots are mirror images
    static bool AreMirrors(Node root1, Node root2) {
      
        // If both roots are empty, they are mirrors
        if (root1 == null && root2 == null)
            return true;
        
        // If only one root is empty, they are not mirrors
        if (root1 == null || root2 == null)
            return false;
        
        // Check if the root data is the same and
        // if the left subroot of root1 is a mirror 
        // of the right subroot of root2 and vice versa
        return (root1.data == root2.data) &&
               AreMirrors(root1.left, root2.right) &&
               AreMirrors(root1.right, root2.left);
    }

     static void Main() {
      
        // Representation of input binary tree 1
        //        1
        //       / \
        //      3   2
        //          / \
        //         5   4
        Node root1 = new Node(1);
        root1.left = new Node(3);
        root1.right = new Node(2);
        root1.right.left = new Node(5);
        root1.right.right = new Node(4);

        // Representation of input binary tree 2 (mirror)
        //        1
        //       / \
        //      2   3
        //     / \
        //    4   5
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);

        if (AreMirrors(root1, root2))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}
JavaScript 
// Recursive JavaScript function to check if two
// roots are mirror images of each other

class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

// Function to check if two roots are mirror images
function areMirrors(root1, root2) {

    // If both roots are empty, they are mirrors
    if (root1 === null && root2 === null) {
        return true;
    }
    
    // If only one root is empty, they are not mirrors
    if (root1 === null || root2 === null) {
        return false;
    }
    
    // Check if the root data is the same and
    // if the left subroot of root1 is a mirror 
    // of the right subroot of root2 and vice versa
    return (root1.data === root2.data) &&
           areMirrors(root1.left, root2.right) &&
           areMirrors(root1.right, root2.left);
}

// Representation of input binary tree 1
//        1
//       / \
//      3   2
//          / \
//         5   4
const root1 = new Node(1);
root1.left = new Node(3);
root1.right = new Node(2);
root1.right.left = new Node(5);
root1.right.right = new Node(4);

// Representation of input binary tree 2 (mirror)
//        1
//       / \
//      2   3
//     / \
//    4   5
const root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);

if (areMirrors(root1, root2)) {
      console.log("true");
} 
else {
      console.log("false");
}

Output
true

Time Complexity: O(n), where n is the number of nodes in the trees.
Auxiliary Space: O(h), where h is height of binary tree.

[Expected Approach - 2] Iterative Approach - O(n) Time and O(n) Space

The idea is to check if two binary trees are mirrors using two stacks to simulate recursion. Nodes from each tree are pushed onto the stacks in a way that compares the left subtree of one tree with the right subtree of the other, and vice versa. This approach systematically compares nodes while maintaining their mirrored structure, ensuring the trees are symmetric relative to their root. Please refer to Iterative method to check if two trees are mirror of each other for implementation.

Comment

Explore