Let's say, key $k$ was found in a leave of a binary search tree. Let $P$ be the search path from the root of the tree to the node with key $k$.
Let set $A$ contain all nodes left from path $P$. Let set $B$ contain all nodes of $P$. Let set $C$ contain all nodes right from path $P$.
Give a short counterexample of this statement:
For every triple $(a,b,c)\in A\times B\times C$ it is $a \leq b \leq c$.
This seems to be an easy exercise, but I don't find a counterexample. It seems, that it is impossible. Our binary search tree can contain more than one node with the same key, but even with this I don't find a counterexample.
Thanks in advance.
If the search path goes right-left-left, some node in $C$ may be smaller than the rightmost node of $P$.
Concretely, let $0$ be at the root, its two children are $-1$ and $4$. The children of $4$ are $2$ and $5$, the children of $2$ are $1$ and $3$. The search for key $1$ makes $B=\{0,4,2,1\}$, $A=\{-1\}$, $C=\{5,3\}$. And $4\le 3$ is false.