Find node N in a tree

I am having trouble coding in Java the following method

int fin开发者_JAVA技巧dNodeN(Node node, int n)

For example if the binary search tree is constructed as following:

        20
   10       30    
 1   14   25   35

Then node 1 would be returned if n=0, node 10 would be returned if n = 1 and so on (i.e inOrder traversal)

Appreciate any help

The simplest realization is to set counter variable to zero. Walk the tree in the usual order. When you go to right child - increase the counter, when you go to the parent and you were in the left child - increase the counter. When the counter becomes equal to N return current vertex.

Here's a version I have, it's a bit different from what you need, but it's something to work from:

public E findElement(E element)
{
    TreeNode<E> current = root;

    while (current != null)
    {
        if ( element.compareTo(current.getElement() ) == 0)   //If found
        {
            return current.getElement();
        } 
        else if( element.compareTo(current.getElement() ) < 0)    //If element is less
        {
            current = current.getLeftChild();               //Try the left child
        } 
        else                                                //If element is greater
        {
            current = current.getRightChild();             //Try the right child
        }
    }

//not found
return null;

}

Pretty sure you can use recursion to get some more concise code, but this gets the job done.

EDIT: OK, try something like this:

public int findNodeN(Node node, int n, int callNumber) //Call initially with findNodeN(tree.getRoot(), n, 0)
{
    if (node.hasLeft())
        findNodeN(node.getLeftChild(), n, callNumber);
    if (callNumber == n)                     
         return node.getElement();
    else
         callNumber++;
    if (node.hasRight())
        printTreeInOrder(node.getRightChild(), n, callNumber);

}

This isn't tested. Calum