• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Nth Smallest Element of a Binary Search Tree

 
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you James...!

I'll try this out.

" The Art Of People Is The True Mirror Of Their Minds........! "
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic