# Binary Search Tree Stability Data Structure

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.

• So what is your question? Could you explicitly mark what is the quote in your post? What have you tried? Where did you get stuck? – Evil Dec 13 '16 at 3:03
• @Evil Edited for clarity, ty~ – TigerCode Dec 13 '16 at 3:05
• How do we change what code? If you're looking for a coding solution, this isn't the right place. – David Richerby Dec 13 '16 at 12:48

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