Author |
Topic: Nth Largest node of BST (Read 1754 times) |
|
hary
Junior Member
Posts: 107
|
 |
Nth Largest node of BST
« on: Feb 20th, 2010, 8:34am » |
 Quote  Modify
|
Ofcourse an O(n) solution is clear to me.
But i wish to know, can we do it in one pass.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Nth Largest node of BST
« Reply #1 on: Feb 20th, 2010, 1:56pm » |
Quote Modify
|
Of course, just do a reverse inorder traversal and take the Nth value.
|
| « Last Edit: Feb 20th, 2010, 1:57pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ravikumarv
Newbie
Gender:
Posts: 5
|
|
Re: Nth Largest node of BST
« Reply #2 on: Feb 24th, 2010, 12:22am » |
Quote Modify
|
Towr,
How to do reverse in order traversal
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Nth Largest node of BST
« Reply #3 on: Feb 24th, 2010, 12:46am » |
Quote Modify
|
It's like a regular inorder traversal, except everywhere where you would choose the left child you now choose the right and vice versa.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: Nth Largest node of BST
« Reply #4 on: Feb 25th, 2010, 12:59pm » |
Quote Modify
|
@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);
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Nth Largest node of BST
« Reply #5 on: Feb 25th, 2010, 1:39pm » |
Quote Modify
|
on Feb 25th, 2010, 12:59pm, 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.
|
| « Last Edit: Feb 25th, 2010, 1:40pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: Nth Largest node of BST
« Reply #6 on: Feb 26th, 2010, 12:31am » |
Quote Modify
|
@towr
thanks for the explanation....
|
|
IP Logged |
|
|
|
newCoder
Newbie
Gender:
Posts: 3
|
|
Re: Nth Largest node of BST
« Reply #7 on: Feb 27th, 2010, 11:17am » |
Quote Modify
|
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);
}
|
|
|
|
IP Logged |
|
|
|
amitkm
Newbie
Posts: 3
|
|
Re: Nth Largest node of BST
« Reply #8 on: Apr 8th, 2010, 11:11pm » |
Quote Modify
|
on Feb 20th, 2010, 1:56pm, 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);
}
|
|
IP Logged |
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Nth Largest node of BST
« Reply #9 on: Apr 9th, 2010, 2:17am » |
Quote Modify
|
on Apr 8th, 2010, 11:11pm, amitkm wrote:
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);
} |
|
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;
}
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print