TechArena Community Test the equivalence of two binary trees

#1
05-11-2009
 Member Join Date: May 2009 Posts: 640
Test the equivalence of two binary trees

I want to make a java code which tests the equivalence of two binary trees. For trivial cases (tree size 0,1, ...) the code seems pretty obvious. However when the size is increasing, I can not determine an algorithm that returns me the correct results. Could you help me find this algo so that I can continue to code? Or give me links? On google I did not really find what I want by searching this algo.
#2
05-11-2009
 Member Join Date: May 2008 Posts: 685
Re: Test the equivalence of two binary trees

When you say equity, you mean full equality, the 2 trees and structurally identical data? If so this should be a recursive algorithm in this style:

Code:
```boolean estEgal(Node node1, Node node2) {
if(node1 == null)
{
return (node2 == null);
}
if(node2 == null)
{
return false;
}
return (node1.value == node2.value) && isEqual(node1.childLeft, node2.childLeft) && isEqual(node1.childRight, node2.childRight);
}```
And you call him from the root node of the two trees to compare.
#3
05-11-2009
 Member Join Date: May 2009 Posts: 640
Re: Test the equivalence of two binary trees

In fact I have an expression such as

E1 = -(A+B)*(C+D)/(C-D)
E2 = (A*C + A*D + B*C + B*D) / (D ? C)

I have to build two trees with and create a method that determines if two trees are equivalent. For example A1.isEqual(Tree A2) should return true in this case.
#4
05-11-2009
 Member Join Date: May 2008 Posts: 685
Re: Test the equivalence of two binary trees

OK but it does not answer my questions:

1) How does your binary tree represents these formulas? What is their in the leaves?
2) What is the definition of "equivalent"?
#5
05-11-2009
 Member Join Date: May 2009 Posts: 640
Re: Test the equivalence of two binary trees

For E1 = -(A+B)*(C+D)/(C-D), for example, was this (sorry for the layout, this thing is capricious):

Code:
```                (*)
/     \
(-)        (/)
/          /   \
(+)        (+)   (+)
/    \      /  \   /  \
A     B    C     D C    D```
And just for the definition! Nothing in my course! Not to mention google
#6
05-11-2009
 Member Join Date: May 2008 Posts: 685
Re: Test the equivalence of two binary trees

So nodes contain operations and leaves contain constants. Already, it allows multiple representations of the same formula. In fact this representation form of binary tree is more suitable for RPN(Reverse Polish Notation).

For me two binary trees are equivalent to two trees that contain exactly the same elements, but that does not respond to your statement (refer to the true representation of E1 and E2) ... you should ask for more information.

 Tags: