This week's book giveaway is in the Clojure forum.
We're giving away four copies of Clojure in Action and have Amit Rathore and Francis Avila on-line!
See this thread for details.
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Nth Smallest Element of a Binary Search Tree

 
Amarbir Singh
Greenhorn
Posts: 20
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you James...!

I'll try this out.

" The Art Of People Is The True Mirror Of Their Minds........! "
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic