@Piyush..
I tried your algo on BST {5,4,6,3,2,1,8,7,10,12,9,11}.
Its only returning 1+7.
Other pairs are 5+3, 6+2.On Mon, Jul 11, 2011 at 6:56 PM, Piyush Sinha <[email protected]>wrote: > @Aanchal....I think my following algo will work..its a modification of > Morris traversal...check if you can find any bug in it...I have tried my > best to make it error free..For further details regarding Morris traversal, > check out http://geeksforgeeks.org/?p=6358 > > *void findsum(node *T,int key) > { > int n = countnodes(T);//returns the number of nodes in the BST > int i=0; > int j=n-1; > node *cur1,*cur2,*p1,*p2; > cur1=cur2=T; > int flag1,flag2,sum; > flag1=flag2=1; > while(i<j) > { > if(cur1->left == NULL && cur2->right == NULL) > { > sum = checksum(cur1,cur2,key); > if(sum==0) //if cur1->data + cur2->data ==key > { > i++;j--; > flag1=flag2=1; > cur1 = cur1->right; > cur2 = cur2>left; > } > if(sum>0) //if cur1->data + cur2->data > key > { > cur2 = cur2->left; > flag1 = 0; //do not do anything with the left > traversal > j--; > } > if(sum<0) //if cur1->data + cur2->data <key > { > cur1 = cur1->right; > flag2 = 0;//do not do anything with the right > traversal > i++; > } > } > else > { > if(flag1 && cur1->left!=NULL) > { > p1 = cur1->left; > while(p1->right!=NULL && p1->right!=cur1) > p1 = p1->right; > if(p1->right == NULL) > { > p1->right = cur1; > cur1 = cur1->left; > } > } > if(flag2 && cur2->right!=NULL) > { > p2 = cur2->right; > while(p2->left!=NULL && p2->left!=cur2) > p2 = p2->left; > if(p2->left == NULL) > { > p2->left = cur2; > cur2 = cur2->right; > } > } > if(p1->right == cur1 || p2->left == cur2) > { > sum = checksum(cur1,cur2,key); > if(sum==0) //if cur1->data + cur2->data ==key > { > if(cur1->left == NULL) > { > cur1 = cur1->right; > flag1 = 0; > } > else if(p1->right == cur1) > { > p1->right = NULL; > cur1 = cur1->right; > flag1 = 1; > } > > if(cur2->right == NULL) > { > cur2 = cur2->left; > flag2 = 0; > } > else if(p2->left == cur2) > { > p2->left = NULL; > cur2 = cur2->left; > flag2 = 1; > } > i++;j--; > } > if (sum<0) //if cur1->data + cur2->data < key > { > if(cur1->left == NULL) > { > cur1 = cur1->right; > flag1 = 0; > } > else if(p1->right == cur1) > { > p1->right = NULL; > cur1 = cur1->right; > flag1 = 1; > } > i++; > } > if(sum>0)//if cur1->data + cur2->data > key > { > if(cur2->right == NULL) > { > cur2 = cur2->left; > flag2 = 0; > } > else if(p2->left == cur2) > { > p2->left = NULL; > cur2 = cur2->left; > flag2 = 1; > } > j--; > } > } > } > } > > //final correction of the links can be done again > } > > int checksum ( node *c1,node *c2,int key) > { > if(c1->data+c2->data == key) > return 0; > else if(c1->data+c2->data > key) > return 1; > else > return -1; > }* > > > > -- > *Piyush Sinha* > *IIIT, Allahabad* > ** > *+91-7483122727* > *Never say NEVER <https://www.facebook.com/profile.php?id=100000655377926> > * > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards,* Aanchal Goyal*. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
