wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Nth Largest node of BST
        
(Message started by: hary on Feb 20^th, 2010, 8:34am)

Title: Nth Largest node of BST
Post by hary on Feb 20^th, 2010, 8:34am

Ofcourse an O(n) solution is clear to me.
But i wish to know, can we do it in one pass.

Title: Re: Nth Largest node of BST
Post by towr on Feb 20^th, 2010, 1:56pm

Of course, just do a reverse inorder traversal and take the Nth value.

Title: Re: Nth Largest node of BST
Post by ravikumarv on Feb 24^th, 2010, 12:22am

Towr,

How to do reverse in order traversal

Title: Re: Nth Largest node of BST
Post by towr on Feb 24^th, 2010, 12:46am

It's like a regular inorder traversal, except everywhere where you would choose the left child you now choose the right and vice versa.

Title: Re: Nth Largest node of BST
Post by srikanth.iiita on Feb 25^th, 2010, 12:59pm

@Towr ..
why do we have to reverse inorder traversal..
tell me whether this approach is right or not...
int count=0;

inorder(root,n )
{
inorder(root->left);
count++;
if(count==n)
print(root->data);
inorder(root->right);
}

Title: Re: Nth Largest node of BST
Post by towr on Feb 25^th, 2010, 1:39pm

on 02/25/10 at 12:59:20, srikanth.iiita wrote:

@Towr ..
why do we have to reverse inorder traversal..

Because we want the Nth largest, in a BST the largest is typically at the end, and if you don't know how many nodes there are in the tree, then you have to start counting from that end.

Your code would print the Nth smallest.

Title: Re: Nth Largest node of BST
Post by srikanth.iiita on Feb 26^th, 2010, 12:31am

@towr
thanks for the explanation....

Title: Re: Nth Largest node of BST
Post by newCoder on Feb 27^th, 2010, 11:17am

I think this should work...

Code:

void FindNthLargest(NodePrt Root , int N)
{
static int count = N;
static bool foundMax = false;
if(!Root)
return;
if( !Root->left && !Root->right){
foundMax = true;
count--;
return;
}
FindNthLargest(Root->Right, N);
//Check for Nth Max
if( foundMax )
count--;
if(!count){
std::cout<< Root->Data;
return;
}
FindNthLargest(Root->left, N);
}

Title: Re: Nth Largest node of BST
Post by amitkm on Apr 8^th, 2010, 11:11pm

on 02/20/10 at 13:56:48, towr wrote:

Of course, just do a reverse inorder traversal and take the Nth value.

I am not able to stop the traversal when after the nth max is found. The code below will do a full traversal.

void FindNth(Node root,int nth, int counter)
{
if root == null
return;

FindNth(root.Right, n, counter);

if(count == n)
print root.Data

FindNth(root.Left, n, counter);
}

Title: Re: Nth Largest node of BST
Post by kaka189 on Apr 9^th, 2010, 2:17am

on 04/08/10 at 23:11:40, amitkm wrote:

hmm.. add a return value 1 if found and 0 if not found, call left only if right returns 0.Made changes to your code, ignored other major errors :) fix them

int FindNth(Node root,int nth, int counter)
{
int ret =0;
if root == null
return;

ret = FindNth(root.Right, n, counter);

if(count == n)
{
print root.Data
return 1; }

if(!ret) ret = FindNth(root.Left, n, counter);

return ret;
}