Java return boolean true using recursion

Question

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?

Community · Accepted Answer · 2017-05-23 11:44:17Z

7

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);

edited May 23, 2017 at 11:44

CommunityBot

11 silver badge

answered Jul 19, 2016 at 19:30

weston

55k23 gold badges151 silver badges209 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

nick zoum Over a year ago

This is incorrect implementation for looking through a binary search tree. By definition the values of the binary search trees are getting smaller the more left you go and larger the more right you go and this method does not utilize this property, making the search more inefficient.

weston Over a year ago

@nickzoum You're quite right! I solved the immediate problem posed and didn't take in that it was an organized tree. I'll even delete once OP changes accept to you.

weston Over a year ago

@Kingamere please change the accepted answer to nick's.

nick zoum Over a year ago

thanks, but you could just edit your answer so that it is correct.

weston Over a year ago

@nickzoum If they don't come back and accept yours I will have to. Till then I've linked to yours.

nick zoum · Accepted Answer · 2016-07-19 19:49:36Z

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;
    }
}

jonhopkins · Accepted Answer · 2016-07-19 19:31:04Z

1

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;
}

answered Jul 19, 2016 at 19:31

jonhopkins

3,8523 gold badges30 silver badges39 bronze badges

Comments

maszter · Accepted Answer · 2016-07-19 19:33:28Z

0

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);
}

answered Jul 19, 2016 at 19:33

maszter

3,7206 gold badges40 silver badges54 bronze badges

Comments

Bhanu Pasrija · Accepted Answer · 2016-07-19 19:48:42Z

0

  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.

edited Jul 19, 2016 at 19:48

answered Jul 19, 2016 at 19:33

Bhanu Pasrija

1372 silver badges9 bronze badges

Comments

Wasimkhana · Accepted Answer · 2021-08-07 18:45:56Z

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

Collectives™ on Stack Overflow

Java return boolean true using recursion

6 Answers 6

5 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

5 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related