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 <[email protected]> wrote:
> Vikram : will u plz elaborate more on ur solution ?
>
> Sanju
> :)
>
> On Fri, Aug 26, 2011 at 5:24 AM, Vikram Singh <[email protected]>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 <[email protected]> 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 <[email protected]
> > >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 [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.
>
> > --
> > 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.
--
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.
