Hi Piyush, Thanx.
On Sat, Dec 10, 2011 at 11:09 PM, Piyush Grover <piyush4u.iit...@gmail.com>wrote: > Hi Aman > > Here is the working algo. I forgot to consider the case you mentioned. So > whenever a new node is getting added in the tree > we need to modify the inordersucc of the predecessor of the current node. > Here is the link: > > you can try out different cases also: > http://www.ideone.com/MOxdl > > -Piyush > > On Sat, Dec 10, 2011 at 8:28 PM, AMAN AGARWAL <mnnit.a...@gmail.com>wrote: > >> Hi. >> >> So can you please tell me the modifications required so it works >> correctly. >> >> Regards, >> Aman. >> >> >> On Sat, Dec 10, 2011 at 8:22 PM, Piyush Grover <piyush4u.iit...@gmail.com >> > wrote: >> >>> yup, you are right.. >>> >>> >>> On Sat, Dec 10, 2011 at 8:09 PM, AMAN AGARWAL <mnnit.a...@gmail.com>wrote: >>> >>>> Hi, >>>> >>>> After 22 you add 21 so >>>> 21->left=22->right=null 22->left=21 21->inorder=22. but here if you >>>> draw the diagram you will see that inorder successor of 18 will >>>> now be 21 not 22. I think you have not taken that into consideration. >>>> Please correct me if I am wrong. >>>> >>>> Regards, >>>> Aman, >>>> >>>> >>>> On Sat, Dec 10, 2011 at 7:37 PM, Piyush Grover < >>>> piyush4u.iit...@gmail.com> wrote: >>>> >>>>> I don't think so. >>>>> First you added 15. >>>>> 15->left = null=15->right=15->succ; >>>>> >>>>> add 13. (13 < 15) so >>>>> 13->left = 13->right = null; 13->succ = 15; 15->left = 13; >>>>> >>>>> add 18 (18 > 15) so >>>>> 18->left = 18->right = null; 18->succ = 15->succ = null; 15->right = >>>>> 15->succ = 18 >>>>> >>>>> add 22 (22 > 15) go to 15->right >>>>> (22 > 18) go to 18-> right >>>>> 22->left = 22->right = null; 22->succ = 18->succ = null; 18->right = >>>>> 18->succ = 22; >>>>> and so on... >>>>> >>>>> >>>>> >>>>> On Sat, Dec 10, 2011 at 6:49 PM, AMAN AGARWAL <mnnit.a...@gmail.com>wrote: >>>>> >>>>>> Hi Piyush, >>>>>> >>>>>> I tried with the following data 15,13,18,22,21. I think your code is >>>>>> not giving proper inorder succ of node 18. >>>>>> Please check it. >>>>>> >>>>>> Regards, >>>>>> Aman. >>>>>> >>>>>> >>>>>> On Sat, Dec 10, 2011 at 6:30 PM, Piyush Grover < >>>>>> piyush4u.iit...@gmail.com> wrote: >>>>>> >>>>>>> insertNode(node *head, int value){ >>>>>>> node *new; >>>>>>> if(head == null){ >>>>>>> new = (node*)malloc(sizeof(node)); >>>>>>> new->data = value; >>>>>>> new->left = new->right = new->inoredrsucc = null; >>>>>>> head = new; >>>>>>> >>>>>>> }else{ >>>>>>> node *root = head; >>>>>>> node *l, *r; >>>>>>> while(root != null){ >>>>>>> >>>>>>> if(root->data > value){ >>>>>>> >>>>>>> l = root; r = null; >>>>>>> root = root->left; >>>>>>> }else{ >>>>>>> >>>>>>> r = root; l = null; >>>>>>> root = root->right; >>>>>>> } >>>>>>> } //endwhile >>>>>>> >>>>>>> if(l != null){ >>>>>>> new = (node*)malloc(sizeof(node)); >>>>>>> new->data = value; >>>>>>> new->left = new->right = null; >>>>>>> new->inordersucc = l; >>>>>>> l->left = new; >>>>>>> }else if(r != null){ >>>>>>> new = (node*)malloc(sizeof(node)); >>>>>>> new->data = value; >>>>>>> new->left = new->right = null; >>>>>>> new->inordersucc = r->inordersucc; >>>>>>> r->inordersucc = new; >>>>>>> r->right = new; >>>>>>> >>>>>>> } >>>>>>> } >>>>>>> } >>>>>>> >>>>>>> On Sat, Dec 10, 2011 at 4:04 PM, sayan nayak >>>>>>> <sayanna...@gmail.com>wrote: >>>>>>> >>>>>>>> @dheeraj: I have one doubt... >>>>>>>> during implementation I assumed that inordersuccessor already >>>>>>>> exists for each node. >>>>>>>> So there's no need to track inodersuccessor. >>>>>>>> Just finding the position is ok.Then u can do the needful to change >>>>>>>> the inordersuccessor for the parent and the added node. >>>>>>>> Pls correct me If I'm wrong >>>>>>>> >>>>>>>> >>>>>>>> On Sat, Dec 10, 2011 at 3:43 PM, Dheeraj Sharma < >>>>>>>> dheerajsharma1...@gmail.com> wrote: >>>>>>>> >>>>>>>>> My algorithm is like: >>>>>>>>> >>>>>>>>> 1.Take two pointers. one pointer track..where the node should be >>>>>>>>> inserted..and other..to keep track of inorder successor. >>>>>>>>> first pointer=root; >>>>>>>>> second pointer=null; >>>>>>>>> >>>>>>>>> 2.if the first pointer moves to the left of a particular >>>>>>>>> node(which becomes its parent)..then the set the value of second >>>>>>>>> pointer=parent. >>>>>>>>> else >>>>>>>>> if the first pointer moves to the right of particular node (which >>>>>>>>> becomes its parent)..the let the value of second pointer as it is.. >>>>>>>>> >>>>>>>>> finally when the node has been inserted at leaf..set the inorder >>>>>>>>> successor of the node=second pointer value >>>>>>>>> >>>>>>>>> Correct me if am wrong >>>>>>>>> >>>>>>>>> >>>>>>>>> On Sat, Dec 10, 2011 at 3:38 PM, sayan nayak <sayanna...@gmail.com >>>>>>>>> > wrote: >>>>>>>>> >>>>>>>>>> hi, >>>>>>>>>> here is the code: >>>>>>>>>> ====================================================== >>>>>>>>>> >>>>>>>>>> struct node >>>>>>>>>> { >>>>>>>>>> int data; >>>>>>>>>> struct node *left; >>>>>>>>>> struct node *right; >>>>>>>>>> struct node *inordersuccessor; >>>>>>>>>> }; >>>>>>>>>> >>>>>>>>>> struct node *createnode(int info){ >>>>>>>>>> struct node* temp; >>>>>>>>>> temp->data=info; >>>>>>>>>> temp->left=temp->right=temp->inordersuccessor=NULL; >>>>>>>>>> return temp; >>>>>>>>>> }; >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> struct node *addNode(struct node *node,int info){ >>>>>>>>>> struct node* temp=Createnode(info); >>>>>>>>>> >>>>>>>>>> if(node==NULL){ >>>>>>>>>> node=(struct node*)malloc(sizeof(struct node); >>>>>>>>>> if (node==NULL) >>>>>>>>>> fatalerror("Out of space"); >>>>>>>>>> else >>>>>>>>>> { node->data=info; >>>>>>>>>> node->left=node->right=node->inordersuccessor=NULL; >>>>>>>>>> } >>>>>>>>>> } >>>>>>>>>> >>>>>>>>>> if (node->left==NULL && info<(node->data)){ >>>>>>>>>> node->left=temp; >>>>>>>>>> temp->inordersuccessor=node; >>>>>>>>>> } >>>>>>>>>> else if (node->right==NULL && info>(node->data)){ >>>>>>>>>> >>>>>>>>>> node->right=temp; >>>>>>>>>> temp->inordersuccessor=node->inordersuccessor; >>>>>>>>>> node->inordersuccessor=temp; >>>>>>>>>> } >>>>>>>>>> else >>>>>>>>>> { >>>>>>>>>> if (info<(node->data)) >>>>>>>>>> node->left=addnode(node->left,info); >>>>>>>>>> else >>>>>>>>>> node->right=addnode(node->right,info); >>>>>>>>>> >>>>>>>>>> } >>>>>>>>>> return node; >>>>>>>>>> } >>>>>>>>>> >>>>>>>>>> I have run a few test cases..It's working.Pls let me know in case >>>>>>>>>> of any failure test cases. >>>>>>>>>> I'm also checking. >>>>>>>>>> >>>>>>>>>> Regards, >>>>>>>>>> Sayan >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Sat, Dec 10, 2011 at 1:33 PM, AMAN AGARWAL < >>>>>>>>>> mnnit.a...@gmail.com> wrote: >>>>>>>>>> >>>>>>>>>>> Hi, >>>>>>>>>>> >>>>>>>>>>> Construct a BST where each node has 3 pointers instead of 2. >>>>>>>>>>> the structure is >>>>>>>>>>> struct node >>>>>>>>>>> { >>>>>>>>>>> int data; >>>>>>>>>>> struct node *left; >>>>>>>>>>> struct node *right; >>>>>>>>>>> struct node *inordersuccessor; >>>>>>>>>>> } >>>>>>>>>>> >>>>>>>>>>> write a code to add nodes in a binary search tree . >>>>>>>>>>> inordersuccessor pointing to inorder successor. >>>>>>>>>>> >>>>>>>>>>> Regards, >>>>>>>>>>> Aman. >>>>>>>>>>> -- >>>>>>>>>>> AMAN AGARWAL >>>>>>>>>>> "Success is not final, Failure is not fatal: It is the courage >>>>>>>>>>> to continue that counts!" >>>>>>>>>>> >>>>>>>>>>> -- >>>>>>>>>>> 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. >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> 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. >>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> -- >>>>>>>>> *Dheeraj Sharma* >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> -- >>>>>>>>> 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. >>>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> 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. >>>>>>>> >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> AMAN AGARWAL >>>>>> "Success is not final, Failure is not fatal: It is the courage to >>>>>> continue that counts!" >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> AMAN AGARWAL >>>> "Success is not final, Failure is not fatal: It is the courage to >>>> continue that counts!" >>>> >>>> -- >>>> 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. >>>> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> AMAN AGARWAL >> "Success is not final, Failure is not fatal: It is the courage to >> continue that counts!" >> >> -- >> 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. >> > > -- > 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. > -- AMAN AGARWAL "Success is not final, Failure is not fatal: It is the courage to continue that counts!" -- 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.
