CODEWITHSUNDEEP
javarecursion
randyMoss1994
randyMoss1994

Reputation: 105

Recursive function with boolean operators

Hello I was wondering if someone could help walk me through what happens when I have a couple of recursive calls involving a boolean operator? So for example how would this code run?

boolean covers(TreeNode root, TreeNode p) {
  if(root == null) return false;
  if(root == p) return true;
  return covers(root.left, p) || covers(root.right, p); //this is what confuses me 
}

For context TreeNode root is the root of the Btree and TreeNode p is a node in the Btree.

Upvotes: 2

Views: 1320

Answers (5)

Pablo Alonso
Pablo Alonso

Reputation: 446

The program will first evaluate covers(root.left, p). Then:

  1. If covers(root.left, p) is true, the whole expression will evaluate to true. You're using an OR and since one of the conditions is true, covers(root.right, p) will NOT need to be evaluated.

  2. If covers(root.left, p) is false, the program will need to evaluate covers(root.right, p) to determine the result of the expression.

Here's something (in pseudocode) you can play with to understand this:

function doSomething() {
  log 'hello world!'
};

x = false || doSomething(); // doSomething will be executed
x = true || doSomething(); // doSomething will NOT be executed

Upvotes: 0

aluz
aluz

Reputation: 81

simply this line the quarantee of visiting all nodes in btree.

 covers(root.left, p) || covers(root.right, p)

Upvotes: 0

linead
linead

Reputation: 1636

We're searching with in a tree, for example:

  a    
 / \   
b   c

Imagine that we're interested in finding out if the node c is under (covered) by a.

Unpacking the method:

boolean covers(TreeNode root, TreeNode p) { // does root, cover the node p
  if(root == null) return false; // if null no
  if(root == p) return true; // if root == p then yes
  return covers(root.left, p) || covers(root.right, p); // if i'm not not p, could one of my children be p
}

Because this is recursive, we continue the method again, this time with the root as the left child. This results in a depth first search, with the first right node being evaluated when we've run out of left nodes to test. Note that if : covers(root.left, p) - returns true, then covers(root.right, p) is never evaluated.

    a    
   / \   
  b   c
 / \
d  e

In our example, if we were searching for node c. We would recurse like so :

covers(a, c)
  covers(b, c)
    covers(d, c)
    covers(e, c)
  covers(c, c) <- returns true

Upvotes: 1

caylee
caylee

Reputation: 941

The code will first check if root is null. If so, the element p cannot be covered, so the return value is false.

After that, the code will check if the elements are equal. So p is covered by root, if it is equal to root. So true is returned.

Otherwise, p must be covered by the left or the right child. So you can use the covers() function again (recursive) to check that.

The first term of the last line (covers(root.left, p)) checks if p is covered by the left child, the second term (covers(root.right, p)) checks if p is covered by the right child. The OR operator (||) combines the function calls and returns true if one (or both) function call returned true.

Upvotes: 0

R. Mittal
R. Mittal

Reputation: 126

return covers(root.left, p) || covers(root.right, p);

This line will return true if either of functions' return is true (because of ||).

Function will return true if node == p otherwise they will reach at leaf and become null and will return false.

Upvotes: 0

Related Questions