@Bharath: I don't think your test works. Suppose y.left is isomorphic to both x.left and x.right. Then you would return true, but you don't know that y.right is isomorphic to anything.
You want (Left1 isomorphic with Left2 and Right1 isomorphic with Right2) or (Left1 isomorphic with Right2) and (RIght1 isomorphic with Left2). That's what Navneet proposed in http://groups.google.com/group/algogeeks/msg/39ae100db5588093. Dave On Aug 29, 1:43 pm, bharath sriram <bharath.sri...@gmail.com> wrote: > Would this work: > > boolean IsQuasiIsomorphic(Node x, Node y) > { > if (x == null && y == null) return true // both null > if (x == null || y == null) return false // exactly one null > //Else, the left sub-tree of tree 1 is isomorphic to the left or right > subtree of tree 2 > return ( ( IsQuasiIsomorphic(x.left, y.left) OR > IsQuasiIsomorphic(x.left, y.right)) AND ( IsQuasiIsomorphic(x.right, > y.right) OR IsQuasiIsomorphic(x.right, y.left) )) > } > > > > On Mon, Aug 29, 2011 at 12:53 PM, bugaboo <bharath.sri...@gmail.com> wrote: > > @Dave: thanks. Knew it wasn't as simple as that. Any other solution > > you can think of? > > > On Aug 29, 12:46 pm, Dave <dave_and_da...@juno.com> wrote: > > > @Bugaboo: No. Consider these trees: > > > > a > > > / \ > > > b c > > > / \ > > > d e > > > / \ > > > f g > > > > a > > > / \ > > > b c > > > / \ > > > d e > > > / \ > > > f g > > > > Dave > > > > On Aug 29, 10:37 am, bugaboo <bharath.sri...@gmail.com> wrote: > > > > > The question I originally asked was meant for strict isomorphic trees. > > > > Now, let's assume the trees can be quasi-isomorphic, i.e 2 binary > > > > trees are called quasi-isomorphic if they have the same structure > > > > after flipping any of the right/left sub-trees any number of times. > > > > How do you do it? > > > > > My initial solution which appears seemingly simple but can't come up > > > > with a test case that fails. > > > > > - Count the number of nodes at every level for both trees. If they are > > > > the same, then they are quasi-isomorphic. I know this is a necessary > > > > condition but is this sufficient as well? > > > > > On Aug 29, 7:37 am, bugaboo <bharath.sri...@gmail.com> wrote: > > > > > > The definition is interpreted as either strictly isomorphic or quasi- > > > > > isomorphic but technically (technically) isomorphic binary trees do > > > > > not require any transformation themselves. See below link: > >http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/ > > > > > > Bharath. > > > > > > On Aug 28, 11:53 pm, muthu raj <muthura...@gmail.com> wrote: > > > > > > > In Amazon written test Isomorphic trees were defined as those in > > which a > > > > > > series of flips can transform one tree to another. > > > > > > *Muthuraj R > > > > > > IV th Year , ISE > > > > > > PESIT , Bangalore* > > > > > > > On Sun, Aug 28, 2011 at 11:52 AM,bugaboo<bharath.sri...@gmail.com> > > wrote: > > > > > > > @Navneet, > > > > > > > > What you are talking about are "quasi-isomorphic" trees where > > trees > > > > > > > can be changed a bit (flip right/left sub-trees to be precise) to > > make > > > > > > > them isomorphic. An "isomorphic" tree does not need any > > > > > > > transformation, they are similar in structure by themselves. > > > > > > > > On Aug 28, 1:44 pm, Navneet <navneetn...@gmail.com> wrote: > > > > > > > > @Dave, > > > > > > > > > From the definition of isomorphic trees(not in ques given), > > what i > > > > > > > > know of is that one can be transformed into another. The above > > three > > > > > > > > are then isomorphic to each other. > > > > > > > > > @Bugaboo, can you clarify what exactly do you mean by > > isomorphic > > > > > > > > here? > > > > > > > > > On Aug 28, 9:25 pm, Dave <dave_and_da...@juno.com> wrote: > > > > > > > > > > @Naveet: So we have a question of semantics. Do these three > > trees have > > > > > > > > > the same structure: > > > > > > > > > > a > > > > > > > > > / > > > > > > > > > b > > > > > > > > > / > > > > > > > > > c > > > > > > > > > > and > > > > > > > > > > a > > > > > > > > > \ > > > > > > > > > b > > > > > > > > > \ > > > > > > > > > c > > > > > > > > > > and > > > > > > > > > > a > > > > > > > > > \ > > > > > > > > > b > > > > > > > > > / > > > > > > > > > c > > > > > > > > > > I say "no," but perhaps you say "yes." > > > > > > > > > > Dave > > > > > > > > > > On Aug 28, 9:35 am, Navneet <navneetn...@gmail.com> wrote: > > > > > > > > > > > Dave, that is why i have an OR condition between. Each side > > of OR has > > > > > > > > > > two calls with AND in between. > > > > > > > > > > > Basically at any node, you will have to invoke with two > > combinations > > > > > > > > > > ((left,left) AND (right,right) OR (left,right) AND > > (right,left)) > > > > > > > > > > > Let me know if you think that's not required. > > > > > > > > > > > On Aug 28, 6:02 pm, Dave <dave_and_da...@juno.com> wrote: > > > > > > > > > > > > @Navneet: Don't we want both subtrees to be isomorphic? > > > > > > > > > > > > Dave > > > > > > > > > > > > On Aug 28, 6:40 am, Navneet <navneetn...@gmail.com> > > wrote: > > > > > > > > > > > > > Dave, > > > > > > > > > > > > > I think the last condition should be > > > > > > > > > > > > > return (AreIsomorphic(tree1->left, tree2->left) && > > > > > > > AreIsomorphic(tree1->right,tree2->right)) || > > > > > > > > > > > > > (AreIsomorphic(tree1->left, tree2->right) && > > > > > > > > > > > > AreIsomorphic(tree1->right,tree2->left)) > > > > > > > > > > > > > On Aug 28, 3:39 pm, Ankur Garg <ankurga...@gmail.com> > > wrote: > > > > > > > > > > > > > > Daves solution looks cool to me...shud work :) > > > > > > > > > > > > > > Nice one Dave :) > > > > > > > > > > > > > > Regards > > > > > > > > > > > > > Ankur > > > > > > > > > > > > > > On Sun, Aug 28, 2011 at 4:08 PM, Ankur Garg < > > > > > > > ankurga...@gmail.com> wrote: > > > > > > > > > > > > > > cant we just count the no of nodes in each level > > and compare > > > > > > > them with the > > > > > > > > > > > > > > second one.. > > > > > > > > > > > > > > > if the numbers are same trees can be said to be > > isomorphic > > > > > > > > > > > > > > > On Sun, Aug 28, 2011 at 3:54 AM, Dave < > > > > > > > dave_and_da...@juno.com> wrote: > > > > > > > > > > > > > > >> @Bugaboo: Use recursion. Assuming > > > > > > > > > > > > > > >> struct tree_node { > > > > > > > > > > > > > >> tree_node *left; > > > > > > > > > > > > > >> tree_node *right; > > > > > > > > > > > > > >> int data; > > > > > > > > > > > > > >> }; > > > > > > > > > > > > > > >> int AreIsomorphic(tree_node tree1, tree_node > > tree2) > > > > > > > > > > > > > >> { > > > > > > > > > > > > > >> if( tree1 == NULL && tree2 == NULL ) > > > > > > > > > > > > > >> return TRUE; // both trees are null > > > > > > > > > > > > > >> if( tree1 == NULL || tree2 == NULL) > > > > > > > > > > > > > >> return FALSE; // one tree is null, the > > other is not > > > > > > > > > > > > > >> return AreIsomorphic(tree1->left,tree2->left) > > && > > > AreIsomorphic(tree1->right,tree2->right); > > > > > > > > > > > > > >> } > > > > > > > > > > > > > > >> Dave > > > > > > > > > > > > > > >> On Aug 27, 12:05 pm,bugaboo< > > bharath.sri...@gmail.com> > > > > > > > wrote: > > > > > > > > > > > > > >> > Considering the definition of binary tree > > isomorphism is > > > > > > > the > > > > > > > > > > > > > >> > following: > > > > > > > > > > > > > >> > - 2 binary trees are isomorphic if they have the > > same > > > > > > > structure but > > > > > > > > > > > > > >> > differ just by values. > > > > > > > > > > > > > > >> > What is the logic (or pseudo code) for checking > > if two > > > > > > > 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 > > > > > > > algogeeks@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.-Hidequotedtext- > > > > > > > > > > > > > - Show quoted text -- Hide quoted text - > > > > > > > > > > > - Show quoted text - > > > > > > > > -- > > > > > > > You received this message because you are subscribed to the > > Google Groups > > > > > > > "Algorithm Geeks" group. > > > > > > > To post to this group, send email to algogeeks@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.-Hidequoted text > > - > > > > > - Show quoted text - > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@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.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
