# Nth Smallest Element of a Binary Search Tree

Amarbir Singh

Greenhorn

Posts: 20

posted 9 years ago

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...

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

Ranch Hand

Posts: 8791

posted 9 years ago

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 ]

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 ]

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi