CODEWITHSUNDEEP
javasearchrecursiontreebinary-search-tree
Matthew Cassar
Matthew Cassar

Reputation: 223

Binary Search Tree Search Returns Null

I have written a functioning binary search tree in java apart from one key function, the search. I am using the logic that i will check if the root is null, then if the term i want to search for is equal to the root (so return root) or > root (so search right subtree) or < root (Search right subtree) using a recursive method. The search is started by calling searchBST(String).

Using printlns to see what is happening I found that if the value is there it will pass through the correct if statement (including setting BNode n to the found value) but will then for some reason go through the method again (Returning null).

The only time this method works is when searching for the root node, which makes no sense to me.

    public BNode search(BNode par, String k){
    BNode n = null;

     if (par != null){
        if ((k.compareTo(par.obj.getKey()) < 0) && (par.left != null)){
            search(par.left, k);
        } 

         if ((k.compareTo(par.obj.getKey()) > 0) && (par.right != null)){
            search(par.right, k);
        } 

        if (k.compareTo(par.obj.getKey()) == 0){
          n = par;    
        } 
    }

    return n;

}

public AnyClass searchBST(String k){
    if (search(root, k) != null)
    return search(root, k).obj; 

    return null;
}

Upvotes: 0

Views: 573

Answers (1)

user2336315
user2336315

Reputation: 16067

I think you missed some return statements :

public BNode search(BNode par, String k){
    BNode n = null;

     if (par != null){
        if ((k.compareTo(par.obj.getKey()) < 0) && (par.left != null)){
            return search(par.left, k);
        } 

         if ((k.compareTo(par.obj.getKey()) > 0) && (par.right != null)){
           return search(par.right, k);
        } 

        if (k.compareTo(par.obj.getKey()) == 0){
          n = par;    
        } 
    }

    return n;
}

Upvotes: 2

Related Questions