How can we find given two binary trees that they are equal ?

Question

Hi,

What would be the efficient algorithm to find if two given binary trees are equal - in structure and content?

Thanks.

Answer 1

A more general term for what you are probably trying to accomplish is graph isomorphism. There are some algorithms to do this on that page.

Answer 2

Modulo stack overflow, something like

eq(t1, t2) =
    eq(t1.left, t2.left) && t1.data=t2.data && eq(t1.right, t2.right)

(This generalizes to an equality predicate for all tree-structured algebraic data types - for any piece of structured data, check if each of its sub-parts are equal to each of the other one's sub-parts.)

Answer 3

It's a minor issue, but I'd adapt the earlier solution as follows...

eq(t1, t2) =
  t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

The reason is that mismatches are likely to be common, and it is better to detect (and stop comparing) early - before recursing further. Of course, I'm assuming a short-circuit && operator here.

I'll also point out that this is glossing over some issues with handling structurally different trees correctly, and with ending the recursion. Basically, there need to be some null checks for t1.left etc. If one tree has a null .left but the other doesn't, you have found a structural difference. If both have null .left, there's no difference, but you have reached a leaf - don't recurse further. Only if both .left values are non-null do you recurse to check the subtree. The same applies, of course, for .right.

You could include checks for e.g. (t1.left == t2.left), but this only makes sense if subtrees can be physically shared (same data structure nodes) for the two trees. This check would be another way to avoid recursing where it is unnecessary - if t1.left and t2.left are the same physical node, you already know that those whole subtrees are identical.

A C implementation might be...

bool tree_compare (const node* t1, const node* t2)
{
  //  Same node check - also handles both NULL case
  if (t1 == t2)  return true;

  //  Gone past leaf on one side check
  if ((t1 == NULL) || (t2 == NULL))  return false;

  //  Do data checks and recursion
  return ((t1->data != t2->data) && tree_compare (t1->left,  t2->left )
                                 && tree_compare (t1->right, t2->right));
}

Answer 4

i think return ((t1->data != t2->data) && tree_compare (t1->left, t2->left ) && tree_compare (t1->right, t2->right)); has a bug it should be return ((t1->data == t2->data) && tree_compare (t1->left, t2->left ) && tree_compare (t1->right, t2->right));

because take a example :T1= 2->3 and T2 1->3 in this case it will return true but it should return false;

Correct me if i am wrong!!