# If I randomly swap pairs of inputs how unbalanced will a binary search tree become?

Treesort sorts input by putting input into a binary search tree and then flattening the tree. In some cases the tree can become unbalanced and so a self-balancing tree is required. There is no requirement for a self-balancing tree if the input is first randomly jumbled up first. However, one cannot shuffle a stream of data without waiting for all the data which is undesirable sometimes.

If I take inputs two at a time and randomly swap them before inserting them how unbalanced will the tree tend to become over time?

• Welcome to CS.SE! What have you tried? Have you tried seeing what happens when you feed your proposed algorithm a stream of numbers that are already in sorted order; or that are in reverse-sorted order? Have you tried writing some code to simulate what happens and run a few random simulations? You should be able to get a pretty good idea by trying this!
– D.W.
Mar 8, 2017 at 2:05
• @D.W Yes. It seems to have height proportional to $\frac{n}{\log_2 m}$ where $n$ is the length of the input and $m$ you take before you shuffle and add. But I can't figure out how to prove this. Mar 8, 2017 at 19:59
• It seems your question focuses on the case of swapping two at a time, so I assume that means $m=2$, i.e., you experimentally seem to think the height is proportional to $n$. Try proving this. Can you prove something about the height, for the special case where the inputs are in already-sorted order, or in reverse-sorted order? Hint: look at everything but the least significant bit of each number of the input. I'd suggest you spend a little more time trying to solve this yourself, then edit the question to show your work so far and your progress and where you got stuck.
– D.W.
Mar 8, 2017 at 21:14