@shashi: once we have two pointer where anomalies exist, we can exchange their data value to obtain original BST...
On Wed, Sep 5, 2012 at 12:38 PM, shashi kant <shashiski...@gmail.com> wrote: > Is it required only to retain the BST property ?? or to retain the > original BST (tree) > > > > > *Shashi Kant * > ***"Think positive and find fuel in failure"* > http://thinkndoawesome.blogspot.com/ > *System/Software Engineer* > *Hewlett-Packard India Software Operations. > * > > > > On Tue, Sep 4, 2012 at 1:56 PM, Rahul Kumar Patle < > patlerahulku...@gmail.com> wrote: > >> @atul: correctly caught... >> here you have to notice that if u get only one violation not second >> violation ill the last... then sure the violation is created because of >> swapping of previous and current of first violation... >> so when you got first violation and put first marker on previous time put >> second marker on current... >> suppose and the last if you don't get the second violation then 2nd >> marker will the current node of first violation... >> as in your case when we got first violation at node prev = 20 and current >> = 10.. mark first point at 20 and second pointer at 10.. at the last the >> 2nd pointer does not get change... >> i have checked this with other test cases.. this case is coming only when >> previous and current are the consecutive nodes(parent and its direct child) >> and one of the node is leaf node... >> >> On Tue, Sep 4, 2012 at 1:22 AM, atul anand <atul.87fri...@gmail.com>wrote: >> >>> i guess i missed this part of bharat post :- >>> /* >>> If we don't get the violation for the second time .. means both are >>> side-by-side elements .. swap them .. >>> */ >>> i was saying the same.....so it will work. >>> >>> >>> On 9/4/12, atul anand <atul.87fri...@gmail.com> wrote: >>> > @rahul : Here are the boundary cases need to be taken care of :- >>> > suppose given BST is the following :- >>> > >>> > root=allocate(70); >>> > root->right=allocate(75); >>> > root->left=allocate(50); >>> > root->left->left=allocate(20); >>> > root->left->left->right=allocate(25); >>> > root->left->left->left=allocate(10); >>> > root->left->right=allocate(60); >>> > root->left->right->right=allocate(65); >>> > root->left->right->left=allocate(55); >>> > >>> > now suppose node(20) and node(10) get swapped >>> > >>> > inorder of given tree is :- >>> > 20 10 25 50 55 60 65 70 75 >>> > >>> > now first violation is at node(20) >>> > but you wont get second voilation...because rest is in inc order. >>> > >>> > yes , it can be done by taking care of root of that first violation. >>> > >>> > >>> > On 9/3/12, Rahul Kumar Patle <patlerahulku...@gmail.com> wrote: >>> >> @bharat: +1 >>> >> i have tried some test cases.. working finely.. @anyone pls verify?? >>> >> >>> >> On Mon, Sep 3, 2012 at 11:58 AM, bharat b >>> >> <bagana.bharatku...@gmail.com>wrote: >>> >> >>> >>> while doing in-order traversal, we have to check if(prev > current) >>> --> >>> >>> then mark prev element for swapping in the first time violation.. >>> >>> if it happens for the second time..then mark current element for >>> >>> swapping. >>> >>> swap both .. >>> >>> >>> >>> If we don't get the violation for the second time .. means both are >>> >>> side-by-side elements .. swap them .. >>> >>> >>> >>> Hope works .. If I miss any case .. correct me >>> >>> thanks, >>> >>> >>> >>> >>> >>> On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle < >>> >>> patlerahulku...@gmail.com> wrote: >>> >>> >>> >>>> @navin: can u explain ur algorithms in words pls.. >>> >>>> >>> >>>> On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar >>> >>>> <algorithm.i...@gmail.com>wrote: >>> >>>> >>> >>>>> void correctBST(struct node *root) >>> >>>>> { >>> >>>>> int flag =0; >>> >>>>> static struct node *temp1, *temp2, *temp3, *prev; >>> >>>>> static int found; >>> >>>>> >>> >>>>> if(found) return; >>> >>>>> >>> >>>>> if(root) { >>> >>>>> correctBST(root->left); >>> >>>>> if(!temp1 && prev && root->data < prev->data) { >>> >>>>> temp1 = prev; >>> >>>>> temp2 = root; >>> >>>>> swap(&(temp1->data), &(temp2->data)); >>> >>>>> flag = 1; >>> >>>>> prev = temp1; >>> >>>>> } >>> >>>>> else if(!temp3 && prev && root->data < prev->data) { >>> >>>>> temp3 = root; >>> >>>>> swap(&(temp1->data), &(temp2->data)); >>> >>>>> swap(&(temp1->data), &(temp3->data)); >>> >>>>> found = 1; >>> >>>>> return; >>> >>>>> } >>> >>>>> if(!flag) >>> >>>>> prev = root; >>> >>>>> correctBST(root->right); >>> >>>>> } >>> >>>>> } >>> >>>>> >>> >>>>> On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle < >>> >>>>> patlerahulku...@gmail.com> wrote: >>> >>>>> >>> >>>>>> help to solve the following.. >>> >>>>>> Question: Two of the nodes of a BST are swapped. Correct the BST >>> >>>>>> (taken >>> >>>>>> from GeekforGeeks <http://www.geeksforgeeks.org/archives/23272> >>> 2nd >>> >>>>>> online test 3rd question) >>> >>>>>> >>> >>>>>> >>> >>>>>> >>> >>>>>> >>> >>>>>> -- >>> >>>>>> Thanks and Regards: >>> >>>>>> Rahul Kumar >>> >>>>>> Patle< >>> http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> >>> >>>>>> M.Tech, School of Information Technology >>> >>>>>> Indian Institute of Technology, Kharagpur-721302, >>> >>>>>> India<http://www.iitkgp.ac.in/> >>> >>>>>> Mobile No: +91-8798049298, +91-9424738542 >>> >>>>>> Alternate Email: rahulkumarpa...@hotmail.com >>> >>>>>> >>> >>>>>> -- >>> >>>>>> 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. >>> >>>>> >>> >>>> >>> >>>> >>> >>>> >>> >>>> -- >>> >>>> Thanks and Regards: >>> >>>> Rahul Kumar >>> >>>> Patle<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro >>> > >>> >>>> M.Tech, School of Information Technology >>> >>>> Indian Institute of Technology, Kharagpur-721302, >>> >>>> India<http://www.iitkgp.ac.in/> >>> >>>> Mobile No: +91-8798049298, +91-9424738542 >>> >>>> Alternate Email: rahulkumarpa...@hotmail.com >>> >>>> >>> >>>> -- >>> >>>> 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. >>> >>> >>> >> >>> >> >>> >> >>> >> -- >>> >> Thanks and Regards: >>> >> Rahul Kumar >>> >> Patle<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> >>> >> M.Tech, School of Information Technology >>> >> Indian Institute of Technology, Kharagpur-721302, >>> >> India<http://www.iitkgp.ac.in/> >>> >> Mobile No: +91-8798049298, +91-9424738542 >>> >> Alternate Email: rahulkumarpa...@hotmail.com >>> >> >>> >> -- >>> >> 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. >>> >>> >> >> >> -- >> Thanks and Regards: >> Rahul Kumar >> Patle<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> >> M.Tech, School of Information Technology >> Indian Institute of Technology, Kharagpur-721302, >> India<http://www.iitkgp.ac.in/> >> Mobile No: +91-8798049298, +91-9424738542 >> Alternate Email: rahulkumarpa...@hotmail.com >> >> -- >> 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. > -- Thanks and Regards: Rahul Kumar Patle<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, India<http://www.iitkgp.ac.in/> Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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.
