Re: [algogeeks] Re: 2 Binary trees are isomorphic?
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
/ \
fg
a
/ \
b c
/ \
d e
/ \
fg
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,bugaboobharath.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
Re: [algogeeks] Re: 2 Binary trees are isomorphic?
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.
--
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.
Re: [algogeeks] Re: 2 Binary trees are isomorphic?
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.
--
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.
Re: [algogeeks] Re: 2 Binary trees are isomorphic?
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.
