My algo:
follow inorder traversal to solve this:-
maintain predecessor pointer which which will point to the it next
inorder successor .
1) recursively call node->left
2) If Predecessor is not NULL then make
Predecessor->inorderSuccesor = node;
3) recursively call node->right if not NULL
else
return node;
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.
