top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to identify, whether two trees are isomorphic or not?

+3 votes
345 views
How to identify, whether two trees are isomorphic or not?
posted Apr 16, 2014 by Atul Mishra

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+2 votes
 
Best answer
  1. A tree with a single node is isomorphic only to a tree with a single node.
  2. Two trees with roots A and B, none of which is a single-node tree, are isomorphic if and only if there is a 1-1 correspondence between the subtrees of A and of B such that the corresponding subtrees are isomorphic.

    int checkIsomorphism(root_tree1, root_tree2)
    {
    if ( root_tree1==Null && root_tree2==NULL)
    return 1
    else if (root_tree1==NULL)
    return 0
    else if (root_tree2==NULL)
    return 0
    else if (root_tree1->data!=root_tree2->data)
    return 0
    else
    return (checkIsomorphism(root_tree1->left,root_tree2->right) && checkIsomorphism(root_tree1->right,root_tree2->left)) || (checkIsomorphism(root_tree1->left,root_tree2->left) && checkIsomorphism(root_tree1->right,root_tree2->right)
    }

//Asumption checking for binary trees

The condition for two trees to be Isomorphic is that ---
Given the root of first tree say X and root of second tree say Y, The subtrees must be isomorphic(All the four subtrees.....two in first and two in second) and there must be one to one correspondence between subtrees of X and subtres of Y. What it mean is that whether the (1) left subtree of X is isomorpic with right subtree of Y And right subtree of X is isomorpic with left subtree of Y OR (2) left subtree of X is isomorpic with left subtree of Y And right subtree of X is isomorphic with right subtree of Y. One among 1 or 2 must be two.. One to One correspondance for binary trees (2-ary) has this meaning. For K- ary There are K! different conditions which need to be checked for Isomorphism

answer Apr 16, 2014 by Prakash
Similar Questions
+1 vote

This was asked today at Amazon interview -

Given two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.

Example
Tree1:
5
1 6
5 4 3 6

Tree2:
1
3 4
6 5

Output
Identical integers

Sample C/C++/Java code would be helpful.

+7 votes

Given two n-node trees, how many rotations does it take to convert one tree into the other?

...