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 using inorder traversal to check whether the two binary trees is a mirror of each other or not have been already discussed. In this post a solution using level order traversal has been discussed.
The idea is to use a queue in which two nodes of both the trees which needs to be checked for equality are present together. At each step of level order traversal, get two nodes from the queue, check for their equality and then insert next two children nodes of these nodes which need to be checked for equality. During insertion step, first left child of first tree node and right child of second tree node are inserted. After this right child of first tree node and left child of second tree node are inserted. If at any stage one node is NULL and other is not, then both trees are not a mirror of each other.
Steps to solve this problem:
1. Check if a is null and b is null than return yes.
2. Check if a is null or b is null than return no.
3. Declare a queue q of pointer to a node and push a and b in it.
4. While q is not empty:
*Update a=q.front and pop the element.
*Update b=q.front and pop the element.
*Check if a->data is not equal to b->data than return no.
*Check if a->left is not null and b->right is not null than push a->left and b->right in the q.
*Else check if a->right is null or b ->left is not null than return no.
5. Return yes.
Below is the implementation of above approach:
C++
// C++ implementation to check whether the two// binary trees are mirrors of each other or not#include <bits/stdc++.h>using namespace std;// Structure of a node in binary treestruct Node { int data; struct Node *left, *right;};// Function to create and return// a new node for a binary treestruct Node* newNode(int data){ struct Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// Function to check whether the two binary trees// are mirrors of each other or notstring areMirrors(Node* a, Node* b){ // If both are NULL, then are mirror. if (a == NULL && b == NULL) return "Yes"; // If only one is NULL, then not // mirror. if (a == NULL || b == NULL) return "No"; queue<Node*> q; // Push root of both trees in queue. q.push(a); q.push(b); while (!q.empty()) { // Pop two elements of queue, to // get two nodes and check if they // are symmetric. a = q.front(); q.pop(); b = q.front(); q.pop(); // If data value of both nodes is // not same, then not mirror. if (a->data != b->data) return "No"; // Push left child of first tree node // and right child of second tree node // into queue if both are not NULL. if (a->left && b->right) { q.push(a->left); q.push(b->right); } // If any one of the nodes is NULL and // other is not NULL, then not mirror. else if (a->left || b->right) return "No"; // Push right child of first tree node // and left child of second tree node // into queue if both are not NULL. if (a->right && b->left) { q.push(a->right); q.push(b->left); } // If any one of the nodes is NULL and // other is not NULL, then not mirror. else if (a->right || b->left) return "No"; } return "Yes";}// Driver Codeint main(){ // 1st binary tree formation /* 1 / \ 3 2 / \ 5 4 */ Node* root1 = newNode(1); root1->left = newNode(3); root1->right = newNode(2); root1->right->left = newNode(5); root1->right->right = newNode(4); // 2nd binary tree formation /* 1 / \ 2 3 / \ 4 5 */ Node* root2 = newNode(1); root2->left = newNode(2); root2->right = newNode(3); root2->left->left = newNode(4); root2->left->right = newNode(5); cout << areMirrors(root1, root2); return 0;} |
Java
// Java implementation to check whether the two// binary trees are mirrors of each other or notimport java.util.*;class GFG{// Structure of a node in binary treestatic class Node { int data; Node left, right;};// Function to create and return// a new node for a binary treestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to check whether the two binary trees// are mirrors of each other or notstatic String areMirrors(Node a, Node b){ // If both are null, then are mirror. if (a == null && b == null) return "Yes"; // If only one is null, then not // mirror. if (a == null || b == null) return "No"; Queue<Node> q = new LinkedList<Node>(); // Push root of both trees in queue. q.add(a); q.add(b); while (q.size() > 0) { // remove two elements of queue, to // get two nodes and check if they // are symmetric. a = q.peek(); q.remove(); b = q.peek(); q.remove(); // If data value of both nodes is // not same, then not mirror. if (a.data != b.data) return "No"; // Push left child of first tree node // and right child of second tree node // into queue if both are not null. if (a.left != null && b.right != null) { q.add(a.left); q.add(b.right); } // If any one of the nodes is null and // other is not null, then not mirror. else if (a.left != null || b.right != null) return "No"; // Push right child of first tree node // and left child of second tree node // into queue if both are not null. if (a.right != null && b.left != null) { q.add(a.right); q.add(b.left); } //If any one of the nodes is null and // other is not null, then not mirror. else if (a.right != null || b.left != null) return "No"; } return "Yes";}// Driver Codepublic static void main(String args[]){ // 1st binary tree formation /* 1 / \ 3 2 / \ 5 4 */ Node root1 = newNode(1); root1.left = newNode(3); root1.right = newNode(2); root1.right.left = newNode(5); root1.right.right = newNode(4); // 2nd binary tree formation /* 1 / \ 2 3 / \ 4 5 */ Node root2 = newNode(1); root2.left = newNode(2); root2.right = newNode(3); root2.left.left = newNode(4); root2.left.right = newNode(5); System.out.print(areMirrors(root1, root2));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation to check whether the two # binary trees are mirrors of each other or not # Structure of a node in binary tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to check whether the two binary # trees are mirrors of each other or not def areMirrors(a, b): # If both are NULL, then are mirror. if a == None and b == None: return "Yes" # If only one is NULL, then not mirror. if a == None or b == None: return "No" q = [] # append root of both trees in queue. q.append(a) q.append(b) while len(q) > 0: # Pop two elements of queue, # to get two nodes and check # if they are symmetric. a = q.pop(0) b = q.pop(0) # If data value of both nodes is # not same, then not mirror. if a.data != b.data: return "No" # append left child of first tree node # and right child of second tree node # into queue if both are not NULL. if a.left and b.right: q.append(a.left) q.append(b.right) # If any one of the nodes is NULL and # other is not NULL, then not mirror. elif a.left or b.right: return "No" # Append right child of first tree node # and left child of second tree node # into queue if both are not NULL. if a.right and b.left: q.append(a.right) q.append(b.left) # If any one of the nodes is NULL and # other is not NULL, then not mirror. elif a.right or b.left: return "No" return "Yes" # Driver Code if __name__ == "__main__": # 1st binary tree formation root1 = Node(1) root1.left = Node(3) root1.right = Node(2) root1.right.left = Node(5) root1.right.right = Node(4) # 2nd binary tree formation root2 = Node(1) root2.left = Node(2) root2.right = Node(3) root2.left.left = Node(4) root2.left.right = Node(5) print(areMirrors(root1, root2))# This code is contributed by Rituraj Jain |
C#
// C# implementation to check whether the two// binary trees are mirrors of each other or notusing System;using System.Collections.Generic;class GFG{// Structure of a node in binary treepublic class Node { public int data; public Node left, right;};// Function to create and return// a new node for a binary treestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to check whether the two binary trees// are mirrors of each other or notstatic String areMirrors(Node a, Node b){ // If both are null, then are mirror. if (a == null && b == null) return "Yes"; // If only one is null, then not // mirror. if (a == null || b == null) return "No"; Queue<Node> q = new Queue<Node>(); // Push root of both trees in queue. q.Enqueue(a); q.Enqueue(b); while (q.Count > 0) { // remove two elements of queue, to // get two nodes and check if they // are symmetric. a = q.Peek(); q.Dequeue(); b = q.Peek(); q.Dequeue(); // If data value of both nodes is // not same, then not mirror. if (a.data != b.data) return "No"; // Push left child of first tree node // and right child of second tree node // into queue if both are not null. if (a.left != null && b.right != null) { q.Enqueue(a.left); q.Enqueue(b.right); } // If any one of the nodes is null and // other is not null, then not mirror. else if (a.left != null || b.right != null) return "No"; // Push right child of first tree node // and left child of second tree node // into queue if both are not null. if (a.right != null && b.left != null) { q.Enqueue(a.right); q.Enqueue(b.left); } //If any one of the nodes is null and // other is not null, then not mirror. else if (a.right != null || b.left != null) return "No"; } return "Yes";}// Driver Codepublic static void Main(String []args){ // 1st binary tree formation /* 1 / \ 3 2 / \ 5 4 */ Node root1 = newNode(1); root1.left = newNode(3); root1.right = newNode(2); root1.right.left = newNode(5); root1.right.right = newNode(4); // 2nd binary tree formation /* 1 / \ 2 3 / \ 4 5 */ Node root2 = newNode(1); root2.left = newNode(2); root2.right = newNode(3); root2.left.left = newNode(4); root2.left.right = newNode(5); Console.Write(areMirrors(root1, root2));}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript implementation to check whether the two// binary trees are mirrors of each other or not// Structure of a node in binary treeclass Node { constructor() { this.data = 0; this.left = null; this.right = null; }};// Function to create and return// a new node for a binary treefunction newNode(data){ var temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}// Function to check whether the two binary trees// are mirrors of each other or notfunction areMirrors(a, b){ // If both are null, then are mirror. if (a == null && b == null) return "Yes"; // If only one is null, then not // mirror. if (a == null || b == null) return "No"; var q = []; // Push root of both trees in queue. q.push(a); q.push(b); while (q.length > 0) { // remove two elements of queue, to // get two nodes and check if they // are symmetric. a = q[0]; q.shift(); b = q[0]; q.shift(); // If data value of both nodes is // not same, then not mirror. if (a.data != b.data) return "No"; // Push left child of first tree node // and right child of second tree node // into queue if both are not null. if (a.left != null && b.right != null) { q.push(a.left); q.push(b.right); } // If any one of the nodes is null and // other is not null, then not mirror. else if (a.left != null || b.right != null) return "No"; // Push right child of first tree node // and left child of second tree node // into queue if both are not null. if (a.right != null && b.left != null) { q.push(a.right); q.push(b.left); } //If any one of the nodes is null and // other is not null, then not mirror. else if (a.right != null || b.left != null) return "No"; } return "Yes";}// Driver Code// 1st binary tree formation/* 1 / \ 3 2 / \ 5 4 */var root1 = newNode(1);root1.left = newNode(3);root1.right = newNode(2);root1.right.left = newNode(5);root1.right.right = newNode(4);// 2nd binary tree formation/* 1 / \ 2 3 / \ 4 5 */var root2 = newNode(1);root2.left = newNode(2);root2.right = newNode(3);root2.left.left = newNode(4);root2.left.right = newNode(5);document.write(areMirrors(root1, root2));</script> |
Output
Yes
Complexity Analysis:
- Time complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
