@Harish, it does.
@Divya, r we not on the same page.
On Thu, Jun 10, 2010 at 10:20 AM, Harish U harishs...@gmail.com wrote:
@Saurabh
I believe for Isomorphic trees only the structure counts not the value at
each nodes.
So i think there is no need to compare the value at the corresponding
@Saurabh
I believe for Isomorphic trees only the structure counts not the value at
each nodes.
So i think there is no need to compare the value at the corresponding node
positions of the two trees.
On Wed, Jun 9, 2010 at 11:15 PM, saurabh gupta sgup...@gmail.com wrote:
is-isomorphic(t1, t2) {
@vadivel and anand
{ 1,2,3 } is *isomorphic* to { 1,3,2 }
{ 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 }
{ 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 }
so its nt necessary that right and left will interchange. it may or may not.
if all right and left are interchanged then it
The Definition of isomorphic trees given in the first post is incomplete
We say two rooted unordered trees are isomorphic if
1. a tree with a single node (the root) is only isomorphic 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
is-isomorphic(t1, t2) {
t1ld = t1-left-data
t2ld = t2-left-data
//.
//base case for null or replace by sentinels and check
if( t1ld == t2ld t1rd == t2rd)
return is-isomorphic(t1ld, t2ld) return is-isomorphic(t1rd, t2rd)
if (t1ld == t2rd t1rd == t2ld)
Two binary trees T1 and T2 are isomorphic if T1 can be transformed
into T2 swapping left and right children of the nodes in T1.Give an
algorithm to report whether 2 given binary trees are isomorphic.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
One approach is to parse the element of the two tree in two arrays and
compare the arrays to fiind if they are isomorphic.
parsing takes O(n).
Comparision takes O(n/2)
for (i=0;in;i++)
{
if(2i+1 n)
break;
if(arr_1[2i] != arr_2[2i+1])
{
break;
}
}
if(i == n/2)
bool isIsomorphic(List* h1,List* h2)
{
if(!h1 !h2) return true;
if(h1 h2)
return(h1-data == h2-data isIsomorphic(h1-left,h2-right)
isIsomorphic(h1-right,h2-left));
else return false;
}
On Tue, Jun 8, 2010 at 8:31 PM, divya sweetdivya@gmail.com wrote:
Two
