# I think I have discovered a new sorting algorithm using binary search tree [closed]

If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and vice versa, such a configuration of BST is inherently sorted with its root being approximately in the middle (in case of nearly complete BST’s). To to this we need to do reverse rotations. Unlike AVL and red black trees, where roatations are done to make the tree balanced, we would do reversed rotations.

I would like to explain the pseudo code and logical implementation of the algorithm through the following images. The algorithm is to first sort the left subtree with respect to the root and then the right subtree. These two subparts will be opposite to each other, that is, left would interchange with right. For simplicity I have taken a BST with right subtree, with respect to root, sorted.

– orlp
May 17 at 9:36
• What do you mean by inherently sorted? Why do you feel like a BST is sorted or not sorted? May 17 at 10:36
• How long does it take to build the search tree before starting to transform it? What is the advantage of the procedure discussed over, say, tree-sort? May 17 at 16:14
• If there is a flag for each node where 0 stands for a normal node while 1 is when the node has non null right child, in the original unsorted BST. The nodes with flag 1 have an entry in a hash table with key being their pointers and the values being the right most node. For example node 23's pointer would map to 30.5's pointer. Then I would not have to traverse all the nodes in between for the iteration. This will bring down time complexity less than linear assuming we receive Original BST as input. I think this it an improvement from tree sort's linear time complexity. May 17 at 16:18
• I think it would improve this question if you specified excruciatingly clearly a) The input to the procedure suggested b) The operation not supported before the transformation and supported thereafter c) How a general search tree is not ordered. May 18 at 13:31