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.
