Perform an inorder traversal store in array A={x : x is a node val in
BST } and in array B={K-x : x is a node val in BST}.Reverse B
because it's descending.
Now merge arrays A and B to array C. Repeated elements in C notify the
pair(x,K-x) which add up to K. memory=O(n) time=O(n).
Plz comment.
On Jul 11, 8:23 pm, Piyush Sinha <[email protected]> wrote:
> Check this one once..I hope it will work now..I hv introduced two more
> variables check1 and check2
> *
> 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;
> int check1,check2;
> check1=check2=0;
> 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--;
> check1 = 1;
> }
> if(sum<0) //if cur1->data + cur2->data <key
> {
> cur1 = cur1->right;
> flag2 = 0;//do not do anything with the right
> traversal
> i++;
> check2 = 1;
> }
> }
> 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;
> check1 = 0;
> }
> else // p1->right = cur1
> check1 = 1;
> }
> 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;
> check2 = 0;
> }
> else //p2->left = cur2
> check2 = 1;
> }
> if(check1 && check2)
> {
> 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*
> * <https://www.facebook.com/profile.php?id=100000655377926> "NEVER SAY
> NEVER"
> *
--
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.
