It is a classic diagonal argument. Suppose algorithm P determines whether a given algorithm produces a valid search tree. Consider the following algorithm Q: "i

It is a classic diagonal argument. Suppose algorithm P determines whether a given algorithm produces a valid search tree. Consider the following algorithm Q: "if P(Q) the produce invalid tree else produce valid tree." In words, the algorithm Q does the opposite of what P predicts. Such Q exists by Kleene's Recursion Theorem (or simply because you can write its code in your favorite language).