/* * 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