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.
