@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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<[email protected]> > > 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> wrote: > > > > > > > > > > > > @Navneet: Don't we want both subtrees to be isomorphic? > > > > > > > > > > > > Dave > > > > > > > > > > > > On Aug 28, 6:40 am, Navneet <[email protected]> > > 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 <[email protected]> > > 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 < > > > > > > > [email protected]> 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 < > > > > > > > [email protected]> 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< > > [email protected]> > > > > > > > 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 > > > > > > > [email protected]. > > > > > > > > > > > > > >> To unsubscribe from this group, send email to > > > > > > > > > > > > > >> [email protected]. > > > > > > > > > > > > > >> 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 [email protected]. > > > > > > > To unsubscribe from this group, send email to > > > > > > > [email protected]. > > > > > > > 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 [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
