@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.
