1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Solution Approach
2.1.
Algorithm
2.2.
C++ Code
2.2.1.
Output
2.2.2.
Time Complexity: O(N)
2.2.3.
Space Complexity: O(1)
3.
3.1.
What are tree traversals?
3.2.
What is the difference between Breadth-first Search and Depth-first search?
3.3.
What is the difference between a binary tree and a binary search tree?
3.4.
What is the binary heap?
3.5.
What is the AVL Tree?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Check if two trees are mirror

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

This article will discuss the problem of checking whether the two trees are mirrors of each other or not. There is a prerequisite to solving this problem. You need to understand traversal in the binary tree. You can refer to this blog on coding ninjas to learn more about this.

### Problem Statement

The problem states that we are given a root of the two binary trees, and we need to check if the two trees are mirrors of each other. Make a function that will return true if two trees are mirrors of each other.

See the sample example for a better understanding of the question.

### Sample Examples

Input:

Output: True

Explanation: These two trees are mirror images of each other, as the left subtree of root1 is the same as the right subtree of root 2.

Input:

Output: False

Explanation: root1 left subtree is not the same as root2 right subtree, therefore they do not mirror images of each other.

## Solution Approach

The idea is very simple, we recursively traverse for the left subtree of root1 and right subtree of root2, then the right subtree of root1 and left subtree of root2, and check for each node, that value of root->key must be the same.

### Algorithm

• Take the input of the binary tree.
• Pass the root1 and root2 of binary trees to function, checkMirror(root1, root2).
• Now check the node value in both the trees; if they are not the same, return false.
• Now recursively call for the left subtree of root1 and right subtree of root2.
• Then make the recursive call for the right subtree of root1 and left subtree of root2.
• There are 2 base conditions, if both the tree becomes NULL, then return true; otherwise, if one tree is NULL, and another tree is not NULL, then return false.

### C++ Code

``````// C++ code to check if two trees are mirror
#include <bits/stdc++.h>
using namespace std;
class TreeNode
{
public:
TreeNode *left, *right;
int val;
TreeNode(int val)
{
this->val = val;
this->left = NULL;
this->right = NULL;
}
};
// function to check if two trees are mirror
bool isMirror(TreeNode *root1, TreeNode *root2)
{
// if both the trees are NULL, return true
if (!root1 && !root2)
return true;
// if one is null, other is not null
if (!root1 || !root2)
return false;
bool left = isMirror(root1->left, root2->right);
bool right = isMirror(root1->right, root2->left);
// if we get true from both the sides, and the value of nodes are also same,
// return true
if (left && right && root1->val == root2->val)
return true;
// else return false;
return false;
}
int main()
{
// constructing the tree 1
TreeNode *root1 = new TreeNode(50);
root1->left = new TreeNode(20);
root1->left->left = new TreeNode(30);
root1->right = new TreeNode(40);

// constructing the tree 2
TreeNode *root2 = new TreeNode(50);
root2->left = new TreeNode(40);
root2->right = new TreeNode(20);
root2->right->right = new TreeNode(30);

// calling the function to check if two trees are mirror
if (isMirror(root1, root2))
{
cout << "Trees are mirror of each other" << endl;
}
else
{
cout << "Trees are not mirror of each other" << endl;
}
}``````

#### Output

``Trees are mirrors of each other``

#### Time Complexity: O(N)

We are only doing linear traversal of the tree, so to check if two trees are mirrors, is O(N).

#### Space Complexity: O(1)

We are not taking any extra space.

Check out this problem - Mirror A Binary Tree.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What are tree traversals?

A process called traversal visits every node in a tree and has the option of printing their values. We always start from the root (head) node since all nodes are connected by edges (links). In other words, we are unable to reach a tree node at random. There are three methods humans employ to move through a tree i.e Inorder, preorder, and postorder.

### What is the difference between Breadth-first Search and Depth-first search?

The BFS uses queue data structure while DFS uses the stack data structure. BFS is more suitable for searching vertices closer to the given source, while DFS is more suitable for solutions away from the source.

### What is the difference between a binary tree and a binary search tree?

A tree that has a maximum of 2 children is called a binary tree, whereas a binary search tree is a particular binary tree having the following properties. Keys in the left subtree are always smaller than the root's node, whereas keys in the right subtree are greater than the root's node.

### What is the binary heap?

It's a full-fledged tree (all levels are filled except possibly the last level and the last level has all keys as left as possible). Because of this trait, Binary Heap can be stored in an array. It can either be a Min Heap or a Max Heap in a Binary Heap. In a Min Binary Heap, the root key must be the smallest of all the keys in the Binary Heap. The same property must be true recursively for all nodes in a Binary Tree.

### What is the AVL Tree?

The Adelson, Velski, and Landis (AVL) trees are named after their creators. An AVL tree is a self-balancing binary tree that ensures that the height difference between its left and right subtrees is no greater than 1.

## Conclusion

In this article, we will discuss an interesting problem in which we are given the root of two binary trees, and we need to check if two trees are mirror.

Suggested problems are Construct a Binary Tree From Preorder and PostorderConstruct a Binary Tree From its Linked-List Representation, and many more.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and algorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Live masterclass