/*
* Two BST are given find common elements in both
* Algo works like this:
* Iteratively traverse both the tree in inorder fashion
* If the first tree node is less than the second tree move the
* first tree forward else if the second tree node is less than the
* first tree move second tree forward. If equal move both tree forward
* Do this operation till either one of the tree is complete.
*
*/
void CommonElementsInBST(TreeNode* root1, TreeNode* root2) {
Stack *stack1 = createStack();
Stack *stack2 = createStack();
int commonElementCount = 0;
do {
while (root1 != NULL ) {
push(stack1, root1);
root1 = root1->left;
}
while (root2 != NULL ) {
push(stack2, root2);
root2 = root2->left;
}
if (isEmpty(stack1) != 0 && isEmpty(stack2)) {
root1 = (TreeNode*)top(stack1);
root2 = (TreeNode*)top(stack2);
if (*((int*)root1->object) < *((int*)root2->object)) {
pop(stack1);
root1 = root1->right;
} else if (*((int*)root1->object) > *((int*)root2->object)) {
pop(stack2);
root2 = root2->right;
} else {
pop(stack1);
pop(stack2);
printf("%d ", *((int*) root1->object));
root1 = root1->right;
root2 = root2->right;
commonElementCount++;
}
}
} while (((isEmpty(stack1) != 0) || root1 != NULL) && ((isEmpty(stack2) != 0) || root1 != NULL));
printf("Number of common elements are : %d", commonElementCount);
}
Sunday, September 23, 2012
Find common elements in given two Binary Search Trees
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment