CODEWITHSUNDEEP
javarecursionbinary-search-tree
coder4lyf
coder4lyf

Reputation: 927

BST Contains method not working properly in JAVA

I'm writing a method to see if a value exists in a BST. 

 public boolean contains(int val){
        return containsHelper(val, root);
    }
    public boolean containsHelper(int val, Node root){


        if(val < root.val && root.left != null) {
            containsHelper(val, root.left);
        }
        else if(val > root.val && root.right != null) {
            containsHelper(val, root.right);
        }
        else { //theyre equal
            return true;
        }

        return false;

    }

I dont understand why my method isn't working, its going into the else where they are equal, but still returning false.

Upvotes: 0

Views: 1501

Answers (2)

novic3
novic3

Reputation: 106

This logic is not correct: else { //theyre equal is not correct. In your code, this else block will also get executed when root.left or root.right is null Code should look like this:

if(val < root.val) {
    if(root.left != null)
        return containsHelper(val, root.left);
    // not going to find val
    else return false;
}
else if(val > root.val) {
    if(root.right != null)
        return containsHelper(val, root.right);
    // not going to find val
    else return false;
}
else { //theyre equal
return true;
}

Upvotes: 1

Marquis Blount
Marquis Blount

Reputation: 8095

consider adding an explicit base case. and an explicit case when you want to return true. 

public boolean contains(int val){
    return containsHelper(val, root);
}
public boolean containsHelper(int val, Node root){
    if(root == null) return false;

    if(root.val == val) return true;
    else if (root.val < val) {
        return containsHelper(val, root.right);
    }else {
        return containsHelper(val, root.left);
    }
}

Upvotes: 1

Related Questions