check if a binary tree is a binary search tree

Question

I have some doubts about this algorithm which checks if a binary tree is a binary search tree:

isAbr(x)
    {
            if(x == NULL)
                    return <true, -∞, +∞>;
            if(x.left == NULL && x.right == NULL)
                    return <true, x.key, x.key>;

            <abrLeft, minLeft, maxLeft> = isAbr(x.left);
            <abrRight, minRight, maxRight> = isAbr(x.left);
            abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);
            min = MIN(minLeft, minRight, x.k);
            max = max(maxLeft, maxRight, x.k);

            return <abr, min, max>
    }

in particular, it is not clear to me what happens when a node has only one child:

for example, here, the node with the value 6 returns $<true, 6, 6>$, and the NULL node to the right of the root returns $<true, -∞, + ∞>$; but with the instruction abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft); don't we get FALSE $(8 < -∞)$?

Answer 1

1. abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft); should likely be comparing with maxLeft and minRight, not maxLeft and minLeft

if(x == NULL)
    return <true, -∞, +∞>;

I'm guessing the point of returning infinities here is to make a NULL vertex NEVER fail the > and < comparisons above, in which case in makes more sense to return <true, +∞, -∞>;

Answer 2

The algorithm as is is incorrect because ±∞ is really just a moniker for "less/greater than everything else", and it's not useful to claim that a null node has these as its min and max subtree values because it doesn't actually exist.

Using these special values as placeholders for the min and max in nonexistent subtrees therefore makes very little sense because when we consider that every finite BST has null nodes beneath its leaves, that implies that those special values are the min and max in every finite BST; this statement is patently untrue.

In addition and as an expansion on the previous point, this behavior is inconsistent with the way the algorithm handles leaf nodes; both of the children for these nodes are null, so why don't the leaves also have ±∞ as min and max values?

To fix this one would need to ensure that null children (and their relationship with the current node) are automatically considered valid. Something to the effect of:

abr = abrLeft and abrRight and (x.left == nil or x.key > maxLeft) and (x.right == nil or x.key < minRight)

should do the trick.