Isomorphic Trees

Posted: 10 Oct, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given two arbitrary binary trees. You need to find if both trees are isomorphic or not.

Two binary trees are said to be isomorphic with each other, if one of the trees can be obtained from the other, by performing the following operation any number of times:

Choose a node of the tree, swap its left and right subtree i.e the left subtree will become the right one, and vice versa.
Note:
1. A binary tree is a tree in which each node has at most two children.   

2. The left subtree of a node, is the tree in which the left child of the node is the root of that tree, and the same holds for the right subtree.

3. The given operation can be performed on any node at any level of the given trees.  

4. Two empty trees are also said to be isomorphic.
Input Format:
The first line contains a single integer t representing the number of test cases. 

The first line of each test case will contain the values of the nodes of the first tree in the level order form ( -1 for NULL node).

The second line of each test case will contain the values of the nodes of the second tree in the level order form ( -1 for NULL node). Refer to the example for further clarification.

Example: 
Consider the binary tree:

abcd

The input of the tree depicted in the image above will be like: 

20 10 35 5 15 30 42 -1 -1 -1 13 -1 -1 -1 -1 -1 -1 
Explanation:
Level 1 :
The root node of the tree is 20

Level 2 :
Left child of 20 = 10
Right child of 20 = 35

Level 3 :
Left child of 10 = 5
Right child of 10 = 15
Left child of 35 = 30
Right child of 35 = 42

Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 15 = null (-1)
Right child of 15 = 13
Left child of 30 = null (-1)
Right child of 30 = null (-1)
Left child of 42 = null (-1)
Right child of 42 = null (-1)

Level 5 :
Left child of 13 = null (-1)
Right child of 13 = 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).
Output Format:
For each test case, return “yes” if both trees are isomorphic, “no” otherwise.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function. 
Constraints:
1 <= T <= 100
0 <= N <= 10^3
1 <= nodeValue <= 10^6

Time Limit: 1sec
Approach 1
  • If both trees are empty, or are equal in terms of structure and corresponding node values, then they are obviously isomorphic.
  • Else, let us  traverse both the trees simultaneously, and check for the isomorphism of subtrees of both the trees as follows:
  1. Let the current node of first and the second tree be 'ND1' and 'ND2' respectively.
  2. If the value of these two nodes is not equal, or one of the nodes is NULL, then clearly the subtrees of these two nodes can not be isomorphic and we return false.
  3. Else if the left subtree of 'ND1' is isomorphic with the left subtree of 'ND2', and the right subtree of 'ND1' is isomorphic with the right subtree of 'ND2', then we don’t need to perform any operation.
  4. Otherwise,  if the left subtree of 'ND1' is isomorphic with the right subtree of 'ND2', and the right subtree of 'ND1' is isomorphic with the left subtree of 'ND2', then as per the problem statement, we can swap the left and right subtrees of either of the two nodes and make both the subtrees equal to each other.
  5. So if for 'ND1' and 'ND2', either of the condition 3 or 4 is satisfied then the whole subtree of 'ND1' will be isomorphic with subtree of 'ND2'.
  • Note that we don’t actually perform the swap operation, it's just for getting some intuition and by saying that some subtree of the first tree is isomorphic with some subtree of the second tree, it is automatically claimed that these two subtrees can be made equal.
Try Problem