CODEWITHSUNDEEP
javarecursion
Kingamere
Kingamere

Reputation: 10122

Java return boolean true using recursion

I am trying to see if a value is contained in my Binary Search Tree, and I am traversing the tree using recursion. The problem is the function returns false as the last value on the call stack instead of true.

Here is pseudo code:

public boolean containsValue(Node node, Value v) {

   if (node.value.equals(v)) {
     return true;
   } 
   containsValue(node.left, v); // <- search left tree
   containsValue(node.right, v); // <- search right tree

   return false;
}

This always returns false.

However I can't do this because the second return statement is dead code:

 return containsValue(node.left, v);
 return containsValue(node.left, v);

So how would I fix this?

Upvotes: 4

Views: 12357

Answers (6)

Wasimkhana
Wasimkhana

Reputation: 21

The method returns false because of its recursive nature. In recursive function after finding the value, it will return the value to its parent copy of the method and that will return to its parent as per the code. We need to store the result somehow to take it to the first call of the recursive method.

In simple words, we need to store the result in a variable and return that variable as a final value from the recursive function.

For programmers, I am sharing a code to take help from and deeply understand it out.

 public boolean contains (int i){
    boolean result= false;
    boolean flag = recursiveContains(root, i, result);
    System.out.println(flag);
    return flag;
}
public boolean recursiveContains(Node root, int i, boolean result)
{
    // if root not null
    if (root != null){
        // if i value found in RandomBST
        if (root.value == i) {
            result = true; // result is used for understanding
            return result;
        }
        else if (i < root.value) {
            //if i smaller then root.value search i in leftchild
            result = recursiveContains(root.left, i, result);
        } else { 
            //if i>root.value search for i in rightchild
            result = recursiveContains(root.right, i, result);
        }
    }
    return result;
}

Further, I am adding a picture explanation of the code. But it requires concentration. I have called the above function for i=9. and shown how it returns true. It totally create 3 calls of contains method.

enter image description here

Upvotes: 0

weston
weston

Reputation: 54781

This solves the immediate problem, but is not the correct or efficient way to search a binary tree as it makes no decision about looking left or right, it just dumbly looks left and then right. Correct answer for that is here.

You want to return true if the left node contains it or (||) the right node contains it.

return containsValue(node.left, v) || containsValue(node.right, v);

And note that it will short circuit and not look in the right if the left contains it.

You can even make the whole thing:

return node.value.equals(v) ||
       containsValue(node.left, v) ||
       containsValue(node.right, v);

Upvotes: 7

nick zoum
nick zoum

Reputation: 7285

There you go

public boolean containsValue(Node node, Value value){
    int result = node.value.compareTo(value);
    if(result == 0){
        return true;
    }else if(result < 0){
        if(node.left != null){
            return containsValue(node.left, v);
        }
        return false;
    }else{
        if(node.right != null){
            return containsValue(node.right, v);
        }
        return false;
    }
}

This will check how the value of the current node compares to the parameter value. If the parameter value is smaller then return the result for the left child (<0), if they are the same then return true (==0), if the pass by value is larger then return the result of the right child (>0). This will continue until a value is found or the child that needs to be searched is null.

This method fully utilizes the binary search tree since it does not check all the variables and has a an average efficiency of O(log(n)) whereas just looking through all the nodes has an average efficiency of O(n) which is much worst.

Sidenote: The method that gets the node with that value is essentially the same you just replace true with node, false with null and boolean with Node

Example:

public Node getNode(Node node, Value value){
    int result = node.value.compareTo(value);
    if(result == 0){
        return node;
    }else if(result < 0){
        if(node.left != null){
            return containsValue(node.left, v);
        }
        return null;
    }else{
        if(node.right != null){
            return containsValue(node.right, v);
        }
        return null;
    }
}

Upvotes: 3

Bhanu Pasrija
Bhanu Pasrija

Reputation: 137

  public boolean containsValue(Node node, Value v) {

   if (node.value.equals(v)) {
     return true;
   } 
   else if(containsValue(node.left, v))
     return true; // <- search left tree

   else if(containsValue(node.right, v)) // <- search right tree
    return true;

   return false;
}

Currently your function is also returning true but only for the node that matches with the search value, for all the other nodes it will return false. So while recurring backwards/ or moving up in the call stack, it ultimately returns false as the final answer. It will be correct only in the case of one node in the tree and it matches the search value.

Upvotes: 0

maszter
maszter

Reputation: 3720

Some people love one-liners:

public boolean containsValue(Node node, Value v) {
    return node.value.equals(v) || containsValue(node.left, v) || containsValue(node.right, v);
}

Upvotes: 0

jonhopkins
jonhopkins

Reputation: 3842

You can check if either branch has returned true, and pass that along before trying to return false.

public boolean containsValue(Node node, Value v) {

   if (node.value.equals(v)) {
       return true;
   } else if (containsValue(node.left, v)) {
       return true;
   } else if (containsValue(node.right, v)) {
       return true;
   }

   return false;
}

Upvotes: 1

Related Questions