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

            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:

enter image description here

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 < -∞)$?

  • $\begingroup$ I suggest abundaning this code and checking if the $ InOrder$ $Traversal$ gives u sorted order (put it in an array, then check that A[i]<=A[i+1] for all $i$) $\endgroup$
    – ShAr
    May 11, 2020 at 20:26

2 Answers 2

  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, +∞, -∞>;


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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