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;


--3,c 4,b


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.

  • $\begingroup$ 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? $\endgroup$
    – Evil
    Dec 13, 2016 at 3:03
  • $\begingroup$ @Evil Edited for clarity, ty~ $\endgroup$
    – TigerCode
    Dec 13, 2016 at 3:05
  • 1
    $\begingroup$ How do we change what code? If you're looking for a coding solution, this isn't the right place. $\endgroup$ Dec 13, 2016 at 12:48

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.