@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.
