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.

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

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

Answer 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';
    }
}

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

Answer 5

Well, if this is an interview question, the first thing I'd blurt out (with zero actual thought) is this: iterate the entire binary recursively and and find the smallest element. Take it out of the binary tree. Now, repeat the process where you iterate the entire tree and find the smallest element, and add it as a parent of the last element found (with the previous element becoming the new node's left child). Repeat as many times as necessary until the original tree is empty. At the end, you are left with the worst possible sorted binary tree -- a linked list. Your pointer is pointing to the root node, which is the largest element.

This is a horrible algorithm all-around - O(n^2) running time with the worst possible binary tree output, but it's a decent starting point before coming up with something better and has the advantage of you being able to write the code for it in about 20 lines on a whiteboard.

Answer 6

A binary tree usually is a binary search tree, in which case no conversion is required.

Perhaps you need to clarify the structure of what you are converting from. Is your source tree unbalanced? Is it not ordered by the key you want to search on? How did you arrive at the source tree?

Answer 7

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

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

        /* a bonsai-tree for testing */
struct tree_node nodes[10] =
{{ nodes+1, nodes+2, 1}
,{ nodes+3, nodes+4, 2}
,{ nodes+5, nodes+6, 3}
,{ nodes+7, nodes+8, 4}
,{ nodes+9, NULL, 5}
,{ NULL, NULL, 6}
,{ NULL, NULL, 7}
,{ NULL, NULL, 8}
,{ NULL, NULL, 9}
        };

struct tree_node * harvest(struct tree_node **hnd)
{
struct tree_node *ret;

while (ret = *hnd) {
        if (!ret->left && !ret->right) {
                *hnd = NULL;
                return ret;
                }
        if (!ret->left ) {
                *hnd = ret->right;
                ret->right = NULL;;
                return ret;
                }
        if (!ret->right) {
                *hnd = ret->left;
                ret->left = NULL;;
                return ret;
                }
        hnd = (rand() &1) ? &ret->left : &ret->right;
        }

return NULL;
}

void insert(struct tree_node **hnd, struct tree_node *this)
{
struct tree_node *ret;

while ((ret= *hnd)) {
        hnd = (this->data  < ret->data ) ? &ret->left : &ret->right;
        }
*hnd = this;
}

void show(struct tree_node *ptr, int indent)
{
if (!ptr) { printf("Null\n"); return; }

printf("Node(%d):\n", ptr->data);
printf("%*c=", indent, 'L');  show (ptr->left, indent+2);
printf("%*c=", indent, 'R');  show (ptr->right, indent+2);
}

int main(void)
{
struct tree_node *root, *this, *new=NULL;

for (root = &nodes[0]; this = harvest (&root);  ) {
        insert (&new, this);
        }

show (new, 0);
return 0;
}

Answer 8

struct Node
{
    int value;
    Node* left;
    Node* right;
};

void swap(int& l, int& r)
{
    int t = l;
    l = r;
    r = t;
}

void ConvertToBST(Node* n, Node** max)
{
    if (!n) return;

    // leaf node
    if (!n->left && !n->right)
    {
        *max = n;
        return;
    }

    Node *lmax = NULL, *rmax = NULL;
    ConvertToBST(n->left, &lmax);
    ConvertToBST(n->right, &rmax);

    bool swapped = false;
    if (lmax && n->value < lmax->value)
    {
        swap(n->value, lmax->value);
        swapped = true;
    }

    if (rmax && n->value > rmax->value)
    {
        swap(n->value, n->right->value);
        swapped = true;
    }

    *max = n;
    if (rmax && rmax->value > n->value) *max = rmax;

    // If either the left subtree or the right subtree has changed, convert the tree to BST again
    if (swapped) ConvertToBST(n, max);
}

Answer 9

Do inorder traversal of the binary tree and store the result. sort the result in acending order form the binary search tree by taking middle element of the sorted list as root( this can done using binary search). so we get balanced binary search tree.

Answer 10

heap sort the tree.. nlogn complexity..