Sunday, September 23, 2012

Find common elements in given two Binary Search Trees


 /*  
  * 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);  
 }  
   

No comments:

Post a Comment