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 <ecstasy.piy...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.