How to find a specific value in the AVL tree and return the Node

Question

public Node search_data_var2(Comparable searchable, Node T){
        if(T.getInfo()==searchable){
            return(T);
        }
        else{
            if(T.getInfo()==null){
                return null;
            }
            if(T.getInfo().compareTo(searchable)>0){
                search_data_var2(searchable,T.getLeft());
            }
            if(T.getInfo().compareTo(searchable)<0){
                search_data_var2(searchable,T.getRight());
            }
        }
}

I need to make a method which finds a node with a specific value "searchable" and returns the node "T", when it contains it. If such a value doesn't exist, the function should return "null". I am in trouble however and don't know how to achieve this with a single method. The function above is what I wrote. The problem is that the method can't return Node and null in the same way.

It's not forbidden to use an external function to achieve this, but currently I don't have a good idea how to achieve this.

Try to `return search_data_var2`. – user58697 Dec 25 '20 at 19:47 — user58697, Dec 25 '20 at 19:47

dreamcrash · Answer 1 · 2020-12-25T20:17:53.883

The problem is that the method can't return Node and null in the same way.

Yes you can, but you need to adapt your code to

public Node search_data_var2(Comparable searchable, Node T){
       ....
            if(T.getInfo().compareTo(searchable) > 0){
                return search_data_var2(searchable,T.getLeft()); // <-- add return
            }
            if(T.getInfo().compareTo(searchable) < 0){
                return search_data_var2(searchable,T.getRight()); // <-- add return
            }
       ...
    }

return the value that will be returned by the search_data_var2 recursive method call. Btw you should not use T as a variable name, typically such names (i.e., a single capitalize letter) are used for generic types. Moreover, instead of == you should use the compareTo method (i.e., T.getInfo().compareTo(searchable) == 0).

Finally, your code might throw a NPE because you are first checking

if(T.getInfo()==searchable)

before actually checking if T.getInfo() is null or if T is null itself. Therefore, you need to rearrange the conditionals, like so:

public Node search_data_var2(Comparable searchable, Node node){
        if(node == null || node.getInfo() == null){
            return null;
        }
        else{
            if(node.getInfo().compareTo(searchable) == 0){
                return node;
            }
            else if(node.getInfo().compareTo(searchable) > 0 ){
                return search_data_var2(searchable, node.getLeft());
            }
            else{
                return search_data_var2(searchable, node.getRight());
            }
        }
    }

score 1 · Accepted Answer · answered Dec 25 '20 at 20:02

For lookup purposes, an AVL tree is identical to a normal binary search tree.

Your code is almost there! Mostly you just need to add return keywords before your recursive calls.

Here's a few other changes I would also make:

By convention in Java, T is used for generic types. I would rename the node to something more descriptive (like node).
Instead of checking for referential equality (==), I would check for value equality using the compareTo method since you're using compareTo anyway. This allows you to find a desired value without having a reference to it.
I would move the null check to the top of the method to avoid any possibility of a NullPointerException.

public Node search_data_var2(Comparable searchable, Node node) {
    // If node is null, we've run off the end of the tree
    // Therefore, the value is not contained in the tree - return null
    if (node == null || node.getInfo() == null) {
        return null;
    }

    if (node.getInfo().compareTo(searchable) == 0) {
        // This node has info equal to the search condition - return it!
        return node;
    } else if (node.getInfo().compareTo(searchable) > 0) {
        // The sought value must be in the left subtree - start the search again there
        return search_data_var2(searchable, node.getLeft());
    } else if (node.getInfo().compareTo(searchable) < 0) {
        // The sought value must be in the right subtree - start the search again there
        return search_data_var2(searchable, node.getRight());
    }
}

How to find a specific value in the AVL tree and return the Node

2 Answers2