How to convert a binary tree to binary search tree in-place, i.e., we cannot use any extra space

Question

How to convert a binary tree to binary search tree in-place, i.e., we cannot use any extra space.

Solution 1

You don't give much to go on, but if the requirement is what I think it is, you have a binary tree already created and sitting in memory, but not sorted (the way you want it to be sorted, anyway).

I'm assuming that the tree nodes look like

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

I'm also assuming that you can read C

While we could just sit around wondering why this tree was ever created without having been created in sorted order that doesn't do us any good, so I'll ignore it and just deal with sorting it.

The requirement that no extra space be used is odd. Temporarily there will be extra space, if only on the stack. I'm going to assume that it means that calling malloc or something like that and also that the resulting tree has to use no more memory than the original unsorted tree.

The first and easiest solution is to do a preorder traversal of the unsorted tree removing each node from that tree and doing a sorted insertion into a new tree. This is O(n+nlog(n)), which is O(nlog(n)).

If this isn't what they want and you're going to have to use rotations and stuff..... that's horrible!

I thought that you could do this by doing an odd version of a heap sort, but I ran into problems. Another thing that did come to mind, which would be horribly slow, would to do an odd version of bubble sort on the tree.

For this each node is compared and possibly swapped with each of it's direct children (and therefore also with its parent) repeatedly until you traverse the tree and don't find any needed swaps. Doing a shaker sort (bubble sort that goes left to right and the right to left) version of this would work best, and after the initial pass you would not need to traverse down subtrees that did not look out of order with respect to it's parent.

I'm sure that either this algorthm was thought up by someone else before me and has a cool name that I just don't know, or that it is fundamentally flawed in some way that I'm not seeing.

Coming up with the run-time calculations for the second suggestion is a pretty complicated. At first I thought that it would simply be O(n^2), like bubble and shaker sorts, but I can't satisfy myself that the subtree traversal avoidance might not win enough to make it a little bit better than O(n^2). Essentially bubble and shaker sorts get this optimization too, but only at the ends where total sortedness occurs early and you can chop down the limits. With this tree version you get oppurtunities to possibly avoid chunks in the middle of the set as well. Well, like I said, it's probably fatally flawed.

Solution 2

Convert Binary Tree to a doubly linked list- can be done inplace in O(n)
Then sort it using merge sort, nlogn
Convert the list back to a tree - O(n)

Simple nlogn solution.

Solution 3

Do the PostOrder Traversal and from that create a Binary search tree.

struct Node * newroot = '\0';

struct Node* PostOrder(Struct Node* root)
{
      if(root != '\0')
      {
          PostOrder(root->left);
          PostOrder(root->right);
          insertBST(root, &newroot);
      }
}

insertBST(struct Node* node, struct Node** root)
{
   struct Node * temp, *temp1;
   if( root == '\0')
   {
      *root == node;
       node->left ==  '\0';
       node->right == '\0';
   }
   else
   {
       temp = *root;
       while( temp != '\0')
       {
           temp1= temp;
           if( temp->data > node->data)
               temp = temp->left;
           else
               temp = temp->right;
       }
       if(temp1->data > node->data)
       {
           temp1->left = node;
       }
       else
       {
           temp1->right = node;
       }
       node->left = node->right = '\0';
    }
}

Solution 4

Do following algorithm to reach the solution.

1) find the in order successor without using any space.

Node InOrderSuccessor(Node node)
{ 
    if (node.right() != null) 
    { 
        node = node.right() 
        while (node.left() != null)  
            node = node.left() 
        return node 
    }
    else
    { 
        parent = node.getParent(); 
        while (parent != null && parent.right() == node)
       { 
            node = parent 
            parent = node.getParent() 
        } 
        return parent 
    } 
} 

2) Do in order traversal without using space.

a) Find the first node of inorder traversal. It should left most child of the tree if it has, or left of first right child if it has, or right child itself. b) Use above algorithm for finding out inoder successor of first node. c) Repeat step 2 for all the returned successor.

Use above 2 algorithm and do the in order traversal on binary tree without using extra space. Form the binary search tree when doing traversal. But complexity is O(N2) worst case.

View more solutions

Comments

[Eli Bendersky]

An arbitrary binary tree is not a BST as it does not necessarily have the BST property of node ordering, I think. Binary trees are used not only for search - they can be used as expression trees, for example

[Alex S]

@Eli, I understand (perhaps you only saw v1 of my answer). It's just that I've never come across a situation where I had an unsorted binary tree and suddenly wanted it sorted. Expression trees are a good case in point; who the heck wants to sort an expression tree? I suspect that some is awry with the OP's bigger picture, hence the various questions I raised.

[theReverseFlick]

A binary tree is a BST? what do you drink?

[Alex S]

@ShyamLovesToCode: I didn't say that a binary tree is a BST. Don't down-vote me for things I never said.

[theReverseFlick]

No conversion is required? its so misguiding

[Alex S]

@ShyamLovesToCode: So now you change the complaint to something far less stupid-sounding without bothering to admit that you got it wrong the first time, or apologising for being so rude about it. Fine, I've amended the answer to make it less "misguiding". Most mornings, I drink a cup of tea with my toast.