Binary Search Tree Stability Data Structure

Question

After constructing a binary search tree, you can read off the key values in ascending order by performing an in-order traversal.

Will the resulting sorted order be stable?
If so, how would the tree have to be coded to ensure this?
If it is not possible, why not?"

Just a review question I came across. From what I understand,

Stability ensures that if A and B share the same Key, if A comes before B originally, A comes before B after sorting as well.

Ascending order = Bottom up

Inorder = Left - Root - Right

if we have a BST that looks as such;

----5,a

--3,c 4,b

-1,d

and we insert a 1,e into the tree. We can get that 1,e on the left or right child of 1,d.

We want to return 1,d first then 1,e so that stability is retained.

How do we change the code for the BST to do this? My suggestion was to make a linked list that returns the head of duplicate values whenever duplicates are encountered. However I'm not sure this is entirely the best method here.

Answer 1

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

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