This week's book giveaway is in the Testing forum.We're giving away four copies of The Way of the Web Tester: A Beginner's Guide to Automating Tests and have Jonathan Rasmusson on-line!See this thread for details.
Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Nth Smallest Element of a Binary Search Tree

Amarbir Singh
Greenhorn
Posts: 20
Hi Friends,

I need little guidance/help ...regarding Binary Search Tree
I have to write an algorithm to :-
1) Create a Biary Search Tree.
2) Find the Nth smallest Element of the tree.

I have solved this problem earlier but just got stuck as I'm implementing this using recursion.

This is the helper method that I'm using...

public void nthSmallest(int n)
{
Node tNode = nthSmallest(root , n);
}
private Node nthSmallest(Node node , int n)
{
Node tempNode = node;
if(tempNode == null)
{
System.out.println(" Tree is Empty hence no data returned....! ");
return node ;
}

if( (counter < n) && (tempNode.left != null) )
{
tempNode = nthSmallest(tempNode.left , n);
counter++;
System.out.println( " left counter < n "+ counter );
}

if(counter < n )
{
counter++;
}

if( (counter < n) && (tempNode.right!=null) )
{
tempNode = nthSmallest(node.right,n);
counter++;
}

if(counter == n)
{
System.out.println(" The Required Element is "+tempNode.data);
}

return tempNode;
}

Node{
int data;
Node left;
Node right;
}

How can I use this type of BST to find nth smallest element...

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
To print the nodes in this tree in order, you do something like:

Now we want to count instead of printing. If the count variable is outside the recursive routine just replace print with counter++ and then compare count to n. We also need a way to signal that we're done without visiting the whole tree. See if this makes sense ... totally off the top of my head and not tested ...

[ October 11, 2007: Message edited by: Stan James ]

Amarbir Singh
Greenhorn
Posts: 20
Thank you James...!

I'll try this out.

" The Art Of People Is The True Mirror Of Their Minds........! "