2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – JK01 Jun 26 '15 at 0:09
  • \$\begingroup\$ The function says little about whether the node itself is valid, and more about if the node ordering is valid. nodeIsOrdered()? nodePositionIsValid() ? \$\endgroup\$ – TessellatingHeckler Jun 26 '15 at 4:30
1
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.