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
@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
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 ( (
@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
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;
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
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
@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,
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,
@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
@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
@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
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
@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)
14 matches
Mail list logo
