Saturday, March 20, 2010

Compare two trees to see if they are structurally identical

Q. Compare two binary trees to see if they are structurally identical

Solution:-

boolean identicalTree(Node a, Node b) {
if (a==null && b==null) return(true);
else if (a!=null && b!=null) {
return(
a.data == b.data &&
sameTree(a.left, b.left) &&
sameTree(a.right, b.right)
);
}
else return(false);
}

This is done in O(n) time complexity.

No comments:

Post a Comment