CODEWITHSUNDEEP
javabinary-search-tree
Inspiration
Inspiration

Reputation: 119

Search about word in BST using Java

I want to check if the word is exist in the BST or not.

There is a mistake it gives me false always:

if(listOfWords.contain(word))
write.print(word+" ");
// using this method but it does not work

private boolean contain(englishWord list, String word) {
    if (list != null) {
        contain(list.getLeft(), word);
        if (word.equals(list.getWord())) {
            return true;
        }
        contain(list.getRight(), word);
    }
    return false;
}

Upvotes: 1

Views: 109

Answers (1)

Codebender
Codebender

Reputation: 14471

Your return true statement is lost up the order in recursion.

You can use something like,

if (list != null) {
    if (word.equals(list.getWord()) || contain(list.getLeft(), word) || contain(list.getRight(), word)) {
        return true;
    }
}
return false;

But this will take O(n) time complexity. And a BST is designed to give much better performances than that.

If your BST is arranged as it should have been, something like this should work (and will be more efficient than your algorithm).

if (list != null) {
    int compare = word.compareTo(list.getWord());
    if (compare == 0) {
        return true;
    } else if (compare > 0) {
        return contain(list.getRight(), word);
    } else {
        return contain(list.getLeft(), word);
    }
}
return false;

Upvotes: 1

Related Questions