traverse the tree and place the elements in an array ------O(n)
take a pivot element and make sure that all the elements which are greater
than pivot is on right side and lesser than pivot are on left side-----O(n)
if # elements on right side is larger than k , then take a pivot in right
side ..and repeat the same until # elements on right side is k-1 ---pivot is
k th largest element
else go to left side and do on left for k-right.size().
Time:O(nlogn) ... but the constant is low ..like quick sort ..
On Sun, Sep 4, 2011 at 5:12 AM, mohit verma <mohit89m...@gmail.com> wrote:
> it would be better if we insert values in array in while loop and then
> outside call makeheapk() and then return topheap();
> this will reduce the heap making complexity.
>
> On Sun, Sep 4, 2011 at 2:29 PM, mohit verma <mohit89m...@gmail.com> wrote:
>
>> int funkth(node *root,int k)
>> {
>>
>> queue<node *> q;
>> q.insert(root);
>> node *temp;
>> while(!q.empty())
>> {
>> temp=q.top();
>> q.pop();
>> if(temp->l) q.insert(temp->l);
>> if(temp->r) q.insert(temp->r);
>> makeheapk(temp->value); //make minheap of size k
>> }
>> return topheap(); //return top element of heap
>> }
>>
>> any corrections please?
>>
>> On Sun, Sep 4, 2011 at 10:20 AM, sukran dhawan <
>> sukrandha...@gmail.com> wrote:
>>
>>> for bst
>>> step 1 :count the number of nodes in a tree
>>> step2: traverse in inorder.after each node visit decrement n. if n == k
>>> then the result
>>>
>>> On Sun, Sep 4, 2011 at 12:33 AM, teja bala <pawanjalsa.t...@gmail.com>wrote:
>>>
>>>> //Asked in MS please help me with the coding or Give an algorithm
>>>>
>>>>
>>>> Write code to return the kth largest element in a tree ...>>> function
>>>> prototype is int fucnkth(node *root,int k)
>>>>
>>>> --
>>>> 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.
>>>
>>
>>
>>
>> --
>> ........................
>> *MOHIT VERMA*
>>
>>
>
>
> --
> ........................
> *MOHIT VERMA*
>
> --
> 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.
>
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar>
*
Mobile +91 8056127652*
<bagana.bharatku...@gmail.com>
--
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.
