Last Updated: 15 Dec, 2020

Check if two trees are Mirror

Easy

Asked in companies

Solve now

Problem statement

You are given two arbitrary binary trees consisting of N and M number of nodes respectively, your task is to check whether the two trees are mirror of each other or not.

Two trees are said to be mirror of each other, if

1. Roots of both the given trees are same.
2. Left subtree of the root of the first tree is the mirror of the right subtree of the root of the second tree.
3. Right subtree of the root of the first tree is the mirror of the left subtree of the root of the second tree.

For example,both the given trees are mirror image of each other: example

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains elements of the first tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 on its place.

The second line of each test case contains elements of the second tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 on its place.

For example, the input for the tree depicted in the below image would be:

example

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation:

Level 1:
The root node of the tree is 1

Level 2:
Left child of 1 = 2
Right child of 1 = 3

Level 3:
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4:
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5:
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).

Note:

The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, the only line of output prints “true” if two trees are mirror of each other else prints “false”.

The output for each test case is in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 80
1 <= N, M <= 3000
-10^6 <= data <= 10^6 and data != -1

Where ‘T’ is the number of test cases, ‘N’ and ‘M’ are the number of nodes in the given binary trees’, and “data” is the value of the binary tree node.

Time Limit: 1sec

Solve now

Approaches

01 Approach

Traverse the tree T in preorder fashion and treat every node of the given tree T as the root, treat it as a subtree and compare the corresponding subtree with the given subtree S for equality. For checking the equality, we can compare all the nodes of the two subtrees.

For two trees ‘S’ and ‘T’ to be mirror images, the following three conditions must be true:

Their root node’s data must be the same.
Left subtree of ‘S’ and the right subtree of ‘T’ are mirror.
Right subtree of ‘S’ and the left subtree of ‘T’ are mirror.

Below is the algorithm:

Check for base cases,
1. If both trees are empty, return true.
2. If only one tree is empty, return false.
Check if the root of the first tree is equal to the root of the second tree or not. If not, return false.
Recursively call left subtree of the first tree and right subtree of the second tree, and vice-versa.

Solve now

02 Approach

The idea is to use a queue in which two nodes of both the trees which need 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 the next two children nodes of these nodes which need to be checked for equality. During the insertion step, the first left child of the first tree node and right child of the second tree node are inserted. After this the right child of the first tree node and the left child of the 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.

Solve now