The use of the excusive or ^ together with the negation makes it hard to read what is going on. Some already have trouble with ^ already have trouble with ^ alone, so adding ! complicates it more. You could replace !(node.left == null ^ node.right == null) with (node.left == null) == (node.right == null), but it is not necessarily clearer.
The use of the excusive or ^ together with the negation makes it hard to read what is going on. Some already have trouble with ^ alone, so adding ! complicates it more. You could replace !(node.left == null ^ node.right == null) with (node.left == null) == (node.right == null), but it is not necessarily clearer.
The use of the excusive or ^ together with the negation makes it hard to read what is going on. Some already have trouble with ^ alone, so adding ! complicates it more. You could replace !(node.left == null ^ node.right == null) with (node.left == null) == (node.right == null), but it is not necessarily clearer.
Keep it simple
You should live by the KISS principle.
private boolean isFull(Node node) { if (node == null) { return true; } return !(node.left == null ^ node.right == null) && isFull(node.left) && isFull(node.right); }
The use of the excusive or ^ together with the negation makes it hard to read what is going on. Some already have trouble with ^ alone, so adding ! complicates it more. You could replace !(node.left == null ^ node.right == null) with (node.left == null) == (node.right == null), but it is not necessarily clearer.
There's a better way to express this. First of all, I don't see why a null node would be a full node, since it isn't a node to begin with. This is also what isComplete is doing (returning false for a null node), so this joins the next point of being consistent. Going back to the description of a full node, it is when a node has either 0 or 2 children that are full.
- When the node is
null, there is no node so it cannot be full. - Has 0 children. This is clearly expressed by being a leaf node, and there is already a method for that we can reuse:
isLeaf(node). - Has 2 children. In this case, both
leftandrightmust be full.
This codes in:
private boolean isFull(Node node) {
return node != null && (isLeaf(node) || isFull(node.left) && isFull(node.right));
}
or, if you prefer,
private boolean isFull(Node node) {
if (node == null) {
return false;
}
return isLeaf(node) || isFull(node.left) && isFull(node.right);
}
All tests still pass after that.
Be consistent
isFull is a method that implements early-returns; so you might as well do the same for isComplete. Instead of having a result variable, just return the result directly. For example:
boolean result = true;
if (root == null) {
result = false;
} else {
// ...
}
return result;
can be written as
if (root == null) {
return false;
}
// ...
This removes one level of indentation and makes the method a little bit clearer. The same can be said for
if (mustBeLeaf) { if (isLeaf(node)) { continue; } else { result = false; break; } }
which, in this case (because the break breaks from the single while loop), is simply
if (mustBeLeaf && !isLeaf(node)) {
return false;
}
The continue; is redundant, as the rest of the code handles this case fine: when it is a leaf, both left and right will be null, so that nothing is added to the queue anyway later (thanks to the null-checks).
Finally, the method would end with return true;.