Re: [algogeeks] isomorphic trees
@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 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) { 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) return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd, t2ld) return false; } On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.comwrote: @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 is mirror tree. i think ur code is for mirror tree and not isomorphic tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] isomorphic trees
@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) { 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) return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd, t2ld) return false; } On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.comwrote: @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 is mirror tree. i think ur code is for mirror tree and not isomorphic tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] isomorphic trees
@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 is mirror tree. i think ur code is for mirror tree and not isomorphic tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] isomorphic trees
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 if and only if there is a 1-1 correspondence between the subtrees of A and the subtrees of B such that corresponding subtrees are isomorphic. Lets say each node has an additional field that says the number of children it has. bool IsIsomorphic(Node* T1,Node* T2) { if( T1 == null T2 == null ) return true; if( T1-numChilderen == T2-numChilderen) { if(IsIsomorphic(( T1-left,T2-left) IsIsoMorphic(T1-right,T2-right)) || (IsIsoMorphic(T1-right,T2-left) IsIsomorphic(T1-left,T2-Right)); } else return false; } Correct me if needed ! On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.com wrote: @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 is mirror tree. i think ur code is for mirror tree and not isomorphic tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] isomorphic trees
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) return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd, t2ld) return false; } On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.com wrote: @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 is mirror tree. i think ur code is for mirror tree and not isomorphic tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] isomorphic trees
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 group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] isomorphic trees
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) printf(trees are isomorphic\n); On Tue, Jun 8, 2010 at 8:01 AM, divya sweetdivya@gmail.com wrote: 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 group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] isomorphic trees
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 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 group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Simplicity is prerequisite for reliability. – Edsger W. Dijkstra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.