CODEWITHSUNDEEP
javabinary-search-tree
user2809114
user2809114

Reputation: 97

binary search tree findNode method always returns root

I have a Binary Search Tree of integers including 1,2,...,9. My traversal methods work, I know that the nodes are there and in the correct order.

I made two methods for searching, one that finds and returns the node, and one that calls that method and prints whether or not the node exists depending on what it returns (null means it doesn't exist).

The findNode(int, BSTNode), however keeps returning the root. When I compare it to example code online, it seems to be correct.

here are the two methods, I call searchPrint(int) from the main method on 7,5,6,1,12,15 (Note that 12 & 15 do not exist in the tree):

 //this method calls findNode(int,BSTNode) and prints a message if the value is found
// in the tree
public void searchPrint(int value)
{
    System.out.print(value);
    if (findNode(value, root) == null)
    {
        System.out.println(" does not exist in the tree.");
    } else
    {
        System.out.println(" exists in the tree.");
    }
}//end searchPrint(int) ----------------------------------------------------

//this method recursively looks for the node that contains 'value' and 
//returns that node if it is found.  Returns null if no nodes contain
//the value.
private BSTNode findNode(int value, BSTNode current)
{
    if(current != null)
    {
        if (value == current.getValue())
        {
            System.out.print("  **Test* entering "
                    + "if(value = current.value loop...**  ");

            return current;
        } else 
        {
            if (value < current.getValue())
            {
                findNode(value,current.getLeft());
            } else 
            {
                findNode(value,current.getRight());
            }
        }
    } else
    {
        return null;
    }
    return current;
}//end findNode(int,BSTNode) -----------------------------------------------

here is the output:

    Traversals:

in-order
1
2
3
4
5
6
7
8
9
pre-order
6
2
1
4
3
5
7
9
8
post-order
1
3
5
4
2
8
9
7
6
7  **Test* entering if(value = current.value loop...**   exists in the tree.
5  **Test* entering if(value = current.value loop...**   exists in the tree.
6  **Test* entering if(value = current.value loop...**   exists in the tree.
1  **Test* entering if(value = current.value loop...**   exists in the tree.
12 exists in the tree.
15 exists in the tree.

Iv'e written down on paper what happens when I search for a value and it makes no sense that it returns the root. What am I doing wrong?

Upvotes: 0

Views: 1352

Answers (2)

niyasc
niyasc

Reputation: 4490

Your recursive call findNode(value,current.getLeft()); or findNode(value,current.getRight()); will return actual result. You are just keeping that result without any use. Instead of that,
use

return findNode(value,current.getLeft());

and

return findNode(value,current.getRight());

Upvotes: 3

Phuong Nguyen
Phuong Nguyen

Reputation: 3070

You are missing return in the recursive call to findNode(), so it always reach the return at the end of the method

Change to:

private BSTNode findNode(int value, BSTNode current)
{
    if(current != null)
    {
        if (value == current.getValue())
        {
            System.out.print("  **Test* entering "
                    + "if(value = current.value loop...**  ");

            return current;
        } else 
        {
            if (value < current.getValue())
            {
                return findNode(value,current.getLeft());
            } else 
            {
                return findNode(value,current.getRight());
            }
        }
    } else
    {
        return null;
    }
    return current;
}

Upvotes: 2

Related Questions