• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Nth Smallest Element of a Binary Search Tree  RSS feed

 
Greenhorn
Posts: 20
  • 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...
 
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • 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
  • 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........! "
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!