CareerCup

bool is_similar(struct node *T1, struct node *T2){
   if(T1==NULL && T2==NULL)
          return true;
   if((T1== NULL && T2 !=NULL) || (T1!=NULL && T2 == NULL))
          return false;
   if(T1->data == T2->data){
         return (is_similar(T1->left, T2->left) && is_similar(T1->right, T2->right));
   }
   
}

For a Complete Binary tree or a Binary Search tree, only one traversal would do
For a Binary tree, min two traversals -- In-order and post/pre-order are required.

Take counter examples to understand the requirement for Binary Tree.

Example 1:
Lets have two Binary trees T1 and T2. T1 has 3 nodes with root=a, left=b and right=c.
T2 has root=a, a's right=b and b's right=c. Now Pre-order traversal of both T1 and T2
will be of same form a,b,c (considering root,left,right order).
Thus T1 and T2 having different structures can have same form in Pre-order traversal.
But thier In-order traversal forms are different. T1(b,a,c) and T2(a,b,c)

Example 2:
Lets have two Binary trees T2 and T3.T2 has root=a, a's right=b and b's right=c.
T3 has 3 nodes with root=a, a's right=b and b's left=c.Now Pre-order (root,left,right)
traversal of both T2 and T3 will be of same form a,b,c. Moreover the Post-order (left,right,root)
traversal of both T2 and T3 will also be of same form c,b,a.
Thus T1 and T2 having different structures can have same form in Pre-order and Post-order traversal.

Thus one of the form must be In-order traversal.

Would appreciate a logical or mathematical proof for this property:-|

could you tell me what does it mean for 'similar binary tree', the structure only?

Whether the structure and elements are equivalent. Check out this link (http://cslibrary.stanford.edu/110/BinaryTrees.html)

Do a pre, post and inorder traversals and collect the node elements in three different arrays for the 2 trees.

If these arrays are equivalent for these trees then they are equal.

hi ak,

Any two traversals would suffice.

Why do we need two traversals ?

can we not do a simple in-order traversal and keep on comparing the nodes on the two trees..

int compare(struct node *n1, struct node *n2)
{
if(n1 == NULL && n2 == NULL)
return true;
if(n1 == NULL && n2 != NULL)
return false;
if(n1 != NULL && n2 == NULL)
return false;
if(!compare(n1->left,n2->left))
return false;
if(n1->data != n2->data)
return false;
if(!compare(n1->right,n2->right))
return false;
return true;
}


I think this should work, please correct me if i am wrong. The only thing I deslike is ther 3 comparisons I do at the beginning.

varunj34@yahoo.com

The explanation is nice but the algo of Varun tests if the left or right child are the same (e.g. NULL or different of NULL).

In Example 1, it would stop at the second call of if(!compare(n1->left,n2->left)) because n1 != NULL (here T1 node b) && n2 == NULL (here T2 left child of a doesn't exist)

1> If input trees are provided with their structures (which is the case here, I believe) then Varun's algorithm works FINE. (thnx Ro for pointing me out)

2> If input is flattened trees (traversed form of the trees) then 2 traversed forms for each Binary Tree and one traversed form for each CBT/BST are required.(Ref to my previous post)

/*
Given two trees, return true if they are
structurally identical.
*/
int sameTree(struct node* a, struct node* b) {
// 1. both empty -> true
if (a==NULL && b==NULL) return(true);

// 2. both non-empty -> compare them
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
sameTree(a->left, b->left) &&
sameTree(a->right, b->right)
);
}
// 3. one empty, one not -> false
else return(false);
}

The above solution is completely workable

Addendum to my post -

Reason: This is a logical reasoning I came up with:
If we look into a building block of Binary Tree, then we see a parent and it's two children.
Now we have the freedom of choosing any node out of 3 given nodes as parent. Once a parent node is decided, we have the freedom of interchanging the left and right child keeping the same spatial tree structure with three nodes. Thus given a 3-node binary tree we need two constraints about the two degrees of freedom (parent-child and ordering of children).
Now we need a way to check for these two constraints and one way could be using its traversed form.

Breadth First Traversal provides only one information-> parent-child
DFT of pre-order provides only one information-> (1) parent-child (same as BFT)
DFT of post-order provides only one information-> (1) parent-child (reverse of pre-order)
DFT of in-order provides only one information-> (1) parent-child

Since BFT and pre-order DFT provides exactly same info, we might consider one of them.
Since post-order DFT is just mirror image of pre-order DFT, we might not get any additional information. In fact traversing Pre-order form from reverse direction will give you post-order form. Thus we choose one of these three form. In order DFT reveals different information (for any node, all nodes on the left are left child/left grand child) we should consider in-order DFT as second form for finding information. Thus two different for should be sufficient to provides us information about two degrees of freedom.

With same logic, a binary search tree has only one degree of freedom. For example, with a three node structure we have the freedom to choose the parent. Once we choose the parent, the left and right children are determined automatically. Thus we need to choose one of the four options.

Now I've noticed that in-order DFT alone is not sufficient but any one of the rest three forms (BFT/pre-order/post-order) alone is sufficient for BST (I couldn't find logic)

bool similar(struct node*T1,struct node*T2)
{

if(T1==NULL && T2==NULL )
return true;

if(T1 !=NULL && T2!=NULL )
{
return( (T1->val==T2->val) && similar(T1->left,T2->left) && similar(T1->right && T2->right ) );

}

else
return false;

}

int identical(struct node* a, struct node* b) 
{ 
  if (a==NULL && b==NULL){return(true);} 
  else if (a!=NULL && b!=NULL) 
  { 
    return(a->data == b->data && 
           identical(a->left, b->left) && 
           identical(a->right, b->right)); 
  } 
  else return(false); 
}