0
$\begingroup$

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 $=$.

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

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

You can test whether $a=b$ as follows: if it's not true that $a<b$ and not true that $b<a$, 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.)

| cite | 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.