Determine if two binary trees are identical

Two trees are identical when they have same data and there physical layout  is also same.

To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees.

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

Time Complexity:
Complexity of the problem will be according to the tree with lesser number of nodes. Let number of nodes in two trees be m and n then complexity will be O(m) where m < n.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation