Wednesday, May 11, 2011

Check whether binary tree are same or not?

Problem

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way.

Solution

11. sameTree() Solution (C/C++)
/*
Given two trees, return true if they are
structurally identical.
*/
int isIdentical(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 &&
isIdentical(a->left, b->left) &&
isIdentical(a->right, b->right)
);
}
// 3. one empty, one not -> false
else return(false);
}



0 comments:

Post a Comment