How about having 2 pointers , from root , one pointer goes twice other goes
once. By the time one goes to the leaf node other will be in median.
Do DFS or inorder traversal.
algo is like:
while(leaf incase or pointer 2 is not reached)
for(every 1 jump of pointer 1 )
jump pointer 2 twice;
}
return pointer 1;
On Sun, Mar 7, 2010 at 4:12 PM, Nik_nitdgp <[email protected]>wrote:
> Given a BST (Binary search Tree) how will you find median in that?
> Constraints:
> -No extra memory.
> Algorithm should be efficient in terms of complexity.
> Write a solid secure code for it.
>
> No extra memory--u cannot use stacks to avoid recursion.
> No static,global--u cannot use recursion and keep track of the
> elements visited so far in inorder.
>
> --
> 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]<algogeeks%[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.
