Binary Tree Search for non key value

Question

I am currently looking for an recursive algorithm to find a non key value in my Tree.

I have my Node Class:

public class TreeNode {
    private Person person;
    private TreeNode left, right;

    public TreeNode(Person person) {
        this.person = person;
    }

    public boolean insert(Person person) {
        if (person.getAge() < this.person.getAge()){
            if (left != null){
                return left.insert(person);
            }else {
                left = new TreeNode(person);
            }
        }else{
            if (right != null){
                return right.insert(person);
            }else{
                right = new TreeNode(person);
            }
        }
        return true;
    }

    public boolean countryExists(String country){
        if (!this.person.getCountry().equals(country)){
            if (right != null) {
                return right.countryExists(country);
            }
            if (left != null) {
                return left.countryExists(country);
            }
        }else {
            return true;
        }
    }
}

The Key value here is the age of a person. I want to find out if there is a Person which comes from a specific country. Therefore I made the function countryExists(String country) I don't know how to implement this and I have searched everywhere and watched a lot of videos about post/pre/inorder. The ordering shouldn't be a problem? I have an issue with returning the correct boolean I think...

Thank you for your help.

Answer 1

In your countryExists method you should return false after two != null checks, because if execution came to this point it means that your node doesn't have left and right siblings (it's a leaf) and it's persons's country doesn't equal to the one you're looking for.

But I would suggest doing some refactoring, and instead of negating this.person.getCountry().equals(country), just use it and return true at the beginning of the method.

public boolean countryExists(String country) {
    if (this.person.getCountry().equals(country)) {
        return true;
    }

    if (right != null) {
        return right.countryExists(country);
    }
    if (left != null) {
        return left.countryExists(country);
    }

    return false;
}

Also, this is O(n) solution, because you're not using a key to cut off entire branches, and doing full tree traversal.

To make it O(log n) (in the case when the tree is balanced), you need to use country as key and choose only one branch when searching.