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