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.
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
b (left from right) before checking c (as explained verbaly). An example is always a plus ;)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.
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.
simply this line the quarantee of visiting all nodes in btree.
covers(root.left, p) || covers(root.right, p)
The program will first evaluate covers(root.left, p). Then:
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.
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
null, it will executecovers(root.left,p), then based on the result, as you have||, will executecovers(root.right,p)if needed . As the walkthrough, use a debugger or add some log to follow the code.return covers(root.left, p) || covers(root.right, p);will return true if either of the statements are true