Yahoo Interview Question
Software Engineer / Developersdoesn't your 2 inorder loops scan the whole tree twice? remember inorder traverses the whole tree, not half tree?
Remember, the question does not say whether it is a BT or BST. So this could be any kind of tree with n-children
Traverse one tree and keep a hash map, for each node add a <key,pair<,>> pair where key is the parent node info and pair are the two children (duplicates can be resolved via chaining). Now traverse next tree and see if same node (value) has same children as found in previous tree based on the hash table values.
As significant optimization:
if( tree1.size() != tree2.size() ){
return false;
}
// TODO: make in-order (or any other) traversation and compare
bool isSame(struct node* head1, struct node* head2)
{
if(head1==null && head2==null) return true;
if(head1==null || head2==null) return false;
if(head1->data != head2->data) return false;
if(!isSame(head1->left, head2->left) || !isSame(head1->right, head2->right)) return false;
else return true;
}
nice answer, if we can rewrite like this
bool isSame(struct node* head1, struct node* head2)
{
if(head1==null && head2==null) return true;
if(head1==null || head2==null) return false;
if(head1->data == head2->data && isSame(head1->left, head2->left) && isSame(head1->right, head2->right))
return true;
else
return false;
}
#define LEFT(n) (n->left == NULL) ? 0 : 1
#define RIGHT(n) (n->right == NULL) ? 0 : 1
bool sameTree(btree *p, btree *q)
{
if(p == NULL && q == NULL)
return true;
if(p->key != q->key)
return false;
if(LEFT(p) != LEFT(q))
return false;
if(RIGHT(p) != RIGHT(q))
return false;
return sameTree(p->left, q->left) && sameTree(p->right, q->right);
}
Well this is just a simple recursion.
int check(struct node *root1, struct node *root2) {
if(root1 == NULL && root2 == NULL) {
return 1;
}
else if(root1 && root2) {
return(root1->data == root2->data && check(root1->left,root2->left) && check(root1->right,root2->right));
}
else {
return 0;
}
}
Traverse both trees recursively together. This will even check if they have the same structures.
isEqual(root1, root2);
boolean isEqual(Node node1, Node node2){
if(node1==null && node2 == null){
return true;
}else if(node1==null){// this means only node2 is null
return false;
}
if(node1.data == node2.data){
return isEqual(node1.left, node2.left)
&& isEqual(node1.right, node2.right);
}
return false;
}
Modified Inorder Traversal(node *head1,node *head2)
- Random Guy June 21, 2011{
if(both head1 head2 are NULL)
return true;
if(one of head1 n head2 NULL)
return false;
if data(head1) == data(head2)
return inorder(head1>left,head2->left)&&inorder(head1->right,head2->right);
return false;
}