Two Binary Trees are similar if they are both empty or if they are both non-empty and left and right sub trees are similar Write an algorithm to determine if two Binary Trees are similar?

Answer 1

/*

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(sameTree(a->left, b->left) &&

sameTree(a->right, b->right)

);

}

// 3. one empty, one not -> false

else return(false);

}