here is my approach.
flag=0;
void inorder(node *root , int value , node *predecessor)
{
if(root)
{
inorder(root->left,value , predecessor);
if(root->value!=value) // store the last node traversed as predessor
until you get the node we are searching
{
predecessor = root;
}
else // once the node we search is found then set a global flag and
exit.predessor will be pointing the previous node in this case
{
flag=1;
exit();
}
inorder(root->right,value,predessor);
}
main()
{
node *p;
inorder(root,value,p);
if(flag)
{
printf("predessor is %d",p->data);
}
else
{
printf("no predessor\n"):
}
}
*Muthuraj R
IV th Year , ISE
PESIT , Bangalore*
On Sun, Aug 28, 2011 at 12:38 PM, vikas <vikas.rastogi2...@gmail.com> wrote:
> no corner cases ...... :D
>
> On Aug 26, 5:43 pm, Vikram Singh <singhvikram...@gmail.com> wrote:
> > i m writing just a pseudocode...
> > // root is the root of tree and node is the node whose
> > predecessor is to be found....
> >
> > predecessor(root, node)
> > {
> > parent=NULL;
> > if(root==NULL)
> > return ;
> >
> > if(node->left!=NULL)
> > {
> > // find max value in left subtree...
> > }
> >
> > else
> > {
> > while(root!=NULL && root->data!=node->data)
> > {
> > if(root->data >node->data)
> > {
> > root=root->left;
> > }
> > else if(root->data< node->data)
> > {
> > parent=root;
> > root=root->right;
> > }
> > }
> > return parent;
> > }
> >
> > }
> >
> > i hope it makes u understand....@sanjay...
> > On Aug 26, 5:27 pm, Sanjay Rajpal <srn...@gmail.com> wrote:
> >
> >
> >
> >
> >
> >
> >
> > > Vikram : will u plz elaborate more on ur solution ?
> >
> > > Sanju
> > > :)
> >
> > > On Fri, Aug 26, 2011 at 5:24 AM, Vikram Singh <
> singhvikram...@gmail.com>wrote:
> >
> > > > ya thats one option but that gives ans in O(n), requires additional
> > > > memory... and unnecessarily finds for all which is not required...
> > > > my sol doesnt require any extra space i.e. in O(1) space... and also
> > > > in O(log n) time...
> >
> > > > tell if dere is any missing case....
> >
> > > > On Aug 26, 4:58 pm, sukran dhawan <sukrandha...@gmail.com> wrote:
> > > > > is it not possible to traverse tree in order and store in array.
> then
> > > > figure
> > > > > out the element and print the previous element?
> >
> > > > > On Fri, Aug 26, 2011 at 2:04 PM, Vikram Singh <
> singhvikram...@gmail.com
> > > > >wrote:
> >
> > > > > > i figured out algo to find the inorder predecessor of a bst
> without
> > > > > > using parent pointer... just wanna confirm if its missing any
> case....
> >
> > > > > > if the left child(subtree) of node exist, then predecessor ll be
> the
> > > > > > max value in the left subtree.
> >
> > > > > > else predecessor ll be one of the ancestor.... in this case,
> starting
> > > > > > from the given node, we hv to find a closest ancestrous node
> which is
> > > > > > right child of its parent... the parent ll be the predecessor...
> >
> > > > > > and i made the parent implementation without changing the
> structure of
> > > > > > the node... using while loop...
> >
> > > > > > let me know if i m missing ant case...
> >
> > > > > > --
> > > > > > 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.
>
>
--
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.
