CODEWITHSUNDEEP
javaalgorithmtreebinary-treebinary-search
3ashmawy
3ashmawy

Reputation: 469

Find node N in a tree

I am having trouble coding in Java the following method

int findNodeN(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

Upvotes: 0

Views: 6552

Answers (2)

Artem Volkhin
Artem Volkhin

Reputation: 1372

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.

Upvotes: 2

Calum Murray
Calum Murray

Reputation: 1192

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

Upvotes: 0

Related Questions