@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.-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.
