0
$\begingroup$

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.

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ What is your question? $\endgroup$
    – orlp
    May 17 at 9:36
  • $\begingroup$ What do you mean by inherently sorted? Why do you feel like a BST is sorted or not sorted? $\endgroup$
    – Rinkesh P
    May 17 at 10:36
  • $\begingroup$ 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? $\endgroup$
    – greybeard
    May 17 at 16:14
  • $\begingroup$ 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. $\endgroup$
    – Uday Uppal
    May 17 at 16:18
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    May 18 at 13:31

1 Answer 1

2
$\begingroup$

Nice work, but not useful because

  • trees are not really sorted (in the sense of a sorted array) as the nodes may be stored non-contiguously in memory, and you need to follow the links;

  • any BST is sorted because traversing the nodes in infix order gives a sorted list, there is no need to reorganize.

$\endgroup$
2
  • $\begingroup$ What if I had a flag to 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. Isn't it an improvement from tree sort's linear time complexity? $\endgroup$
    – Uday Uppal
    May 17 at 11:46
  • $\begingroup$ @UdayUppal: I am not sure that you understood my answer. $\endgroup$ May 17 at 11:58

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