@deepankar cool idea...:) @sagar sol 1 is better,What if we are simply passed a tree in which we have to search... On Sat, Aug 6, 2011 at 8:33 PM, Dipankar Patro <[email protected]> wrote:
> how about using the threaded binary tree? > > > On 6 August 2011 20:25, sagar pareek <[email protected]> wrote: > >> Sorry for typo mistake in prev solution >> >> >> 2 solutions >> >> 1. >> >> node* arr[100]; >> int j=0; >> >> inorder(node * ptr) >> { >> if(ptr) >> { >> inorder(ptr->left); >> arr[j++]=ptr; >> inorder(ptr->right); >> } >> } >> >> u will have all the addresses in inorder fashion.... now its easy to watch >> any successor ... :P :P >> >> 2. best solution >> //considering that there is 1 more field in the structure >> >> >> typedef struct bin >> { >> struct bin* left; >> int data; >> struct bin* right; >> struct bin* succ; >> } node; >> >> >> >> inorder(node* ptr) >> { >> if(ptr) >> { >> static int p=0; >> inorder(ptr->left) >> if(p) ptr->succ=prev; //here we are skipping 1st left most leaf >> because it has no successor >> p=1; >> prev=ptr; >> inorder(ptr->right); >> } >> } >> >> >> simplest and short code :) :) :) >> >> anyone have better code??? >> >> On Sat, Aug 6, 2011 at 8:24 PM, sagar pareek <[email protected]>wrote: >> >>> 2 solutions >>> >>> 1. >>> >>> node* arr[100]; >>> int j=0; >>> >>> inorder(node * ptr) >>> { >>> if(ptr) >>> { >>> inorder(ptr->left); >>> arr[j++]=ptr; >>> inorder(ptr->right); >>> } >>> } >>> >>> u will have all the addresses in inorder fashion.... now its easy to >>> watch any successor ... :P :P >>> >>> 2. best solution >>> //considering that there is 1 more field in the structure >>> >>> >>> typedef struct bin >>> { >>> struct bin* left; >>> int data; >>> struct bin* right; >>> struct bin* succ; >>> } >>> >>> >>> inorder >>> { >>> if(ptr) >>> { >>> static int p=0; >>> inorder(ptr->left) >>> if(p) ptr->succ=prev; //here we are skipping 1st left most leaf >>> because it has no successor >>> p=1; >>> prev=ptr; >>> inorder(ptr->right); >>> } >>> } >>> >>> >>> simplest and short code :) :) :) >>> >>> anyone have better code??? >>> >>> >>> >>> >>> >>> On Sat, Aug 6, 2011 at 6:52 PM, UTKARSH SRIVASTAV < >>> [email protected]> wrote: >>> >>>> sorry two cases only >>>> >>>> >>>> On Sat, Aug 6, 2011 at 6:21 AM, UTKARSH SRIVASTAV < >>>> [email protected]> wrote: >>>> >>>>> pseudo code >>>>> >>>>> three cases are possible >>>>> 1.node has left and right child >>>>> then inorder succesor will be leftmost child of right child >>>>> 2. node has left child and no right child or no left and right chid >>>>> if node is left child of it's parent then inorder succesor is it's >>>>> parent only >>>>> if node is right child of it's parent then keep on moving upwards >>>>> until you find a parent which is left child of it's parent >>>>> then it will be the inorder succesor....if you reach node then no >>>>> inorder succesor >>>>> >>>>> -- >>>>> *UTKARSH SRIVASTAV >>>>> CSE-3 >>>>> B-Tech 3rd Year >>>>> @MNNIT ALLAHABAD* >>>>> >>>>> >>>> >>>> >>>> -- >>>> *UTKARSH SRIVASTAV >>>> CSE-3 >>>> B-Tech 3rd Year >>>> @MNNIT ALLAHABAD* >>>> >>>> -- >>>> 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. >>>> >>> >>> >>> >>> -- >>> **Regards >>> SAGAR PAREEK >>> COMPUTER SCIENCE AND ENGINEERING >>> NIT ALLAHABAD >>> >>> >> >> >> -- >> **Regards >> SAGAR PAREEK >> COMPUTER SCIENCE AND ENGINEERING >> NIT ALLAHABAD >> >> -- >> 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. >> > > > > -- > > ___________________________________________________________________________________________________________ > > Please do not print this e-mail until urgent requirement. Go Green!! > Save Papers <=> Save Trees > > -- > 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. > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
