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

A binary tree usually is a binary search tree; 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 2

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 3

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+n*log(n)), which is O(n*log(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.