# Tiny function to ensure a node of a BST has a valid relationship with its children

I need to write a method to ensure that all of the nodes of a BST (Binary Search Tree) are valid. For a node to be valid, 2 things must hold:

• The left child must be less than the current node's value
• The right child must be greater than the current node's value.

I decided to write a helper method that checks an individual node. Conceptually, it's easy enough, but the end result looks clumsy. I started out with:

//Returns true if the left node is less than the current node, and the right
// node is greater than the current node.
private boolean nodeIsValid() {
if (hasLeft() && left.compareTo(this) > 0) return false;
if (hasRight() && right.compareTo(this) < 0) return false;

return true;
}


Then I realized I could combine the 2 guards into a single check:

private boolean nodeIsValid2() {
if (hasLeft() && left.compareTo(this) > 0 ||
hasRight() && right.compareTo(this) < 0)
return false;

return true;
}


But it seems pretty bulky still. Plus, given I'm just returning true or false based on a condition, I imagine this could be compacted down into a single statement (although I don't know if that would help readability).

Which of my two versions is more pleasant and readable?

Can the check be cleanly reduced to a single statement?

• If you ever have if (x) return true; return false; then it can always be reduced to return x. In your case since you've got if (x) return false; return true; it can be reduced to return !x.
– JK01
Jun 26, 2015 at 0:09
• The function says little about whether the node itself is valid, and more about if the node ordering is valid. nodeIsOrdered()? nodePositionIsValid() ? Jun 26, 2015 at 4:30

Which of my two versions is more pleasant and readable?

The second is just bad as said in the comment by JK01.

It should be just

return !(hasLeft() && left.compareTo(this) > 0 ||
hasRight() && right.compareTo(this) < 0);


and then you could use De-Morgan rule to get rid of the outer negation. However, something like

return (!hasLeft() || left.compareTo(this) <= 0) &&
(!hasRight() || right.compareTo(this) >= 0);


has nothing to do with the idea it represents. Sticking with the original and adding braces is best:

private boolean nodeIsValid() {
if (hasLeft() && left.compareTo(this) > 0) {
return false;
}
if (hasRight() && right.compareTo(this) < 0) {
return false;
}
return true;
}

• It's easily extensible: Just add another condition.
• It's structured: 2 simple expressions instead of a multiline monster.
• It corresponds exactly with what could go wrong.