Algorithm for searching in BST with only <

How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $$<$$ on the key type. The ones I can easily also requires $$=$$.

• Can you edit the question to show a specific example where there is no the presence of = on the key type? – John L. Mar 31 '19 at 15:13

2 Answers

If what you mean is that you want to build a BST and you only have the $$<$$ operation, and you only know the algorithms with the $$\leq$$ operation, you can notice that : $$a \leq b \Leftrightarrow \neg (a > b)$$ $$\Leftrightarrow \neg(b < a )$$ Hence, using a negation in the right place, you can build your usual algorithm.

You can test whether $$a=b$$ as follows: if it's not true that $$a and not true that $$b, then it follows that $$a=b$$.

(Disclaimer: this requires that it be possible to order all of the elements using $$<$$, i.e., $$\le$$ be a total order. I imagine you were assuming this. But if it's not, you're screwed anyway and the problem is not solvable -- binary search trees require a total order.)