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