Check if two Trees are Structurally Similar

[wpdm_package id=’1352′]

Algorithm:

  • Use Recursion.
  • If both the trees are NULL, return true.
  • If only one of the trees is NULL return false.
  • Recursively find if all pairs of corresponding left nodes and right nodes are equal.

[sourcecode lang=”cpp”]
int AreStructurallySimilarTrees(tree_node *root1, tree_node* root2)
{ if(!root1 && !root2)
return 1;
if(!root1 || !root2)
return 0;
return(root1->data==root2->data && AreStructurallySimilarTrees(root1->left,root2->left) && AreStructurallySimilarTrees(root1->right,root2->right));
}
[/sourcecode]

Leave a Reply

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