Binary Search Tree Stability Data Structure
You can ensure that the inorder is stable by modifying the insertion routine (if necessary) so that when it compares an element $x_1$ already in the tree to the new element $x_2$, if $x_1 = x_2$ then it answers that $x_1 &lt; x_2$.

Caveat: I'm not sure that this works for self-balancing trees.