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.

Persnickety

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.

Mccann

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.

Weller

But this will take extra space for creating linkedlist. Right ? Question is without taking extra space . – Knawel

@MSach There are ways to convert tree to linked list "inplace" – Weller

I don't think this will preserve the original structure of the BST. – Thompkins

This is great! Simple and intuitive! – Glossotomy

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

Photodrama

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.

Thaxton

Answer 5

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?

Rescind

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 – Hart

@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. – Rescind

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

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

No conversion is required? its so misguiding – Brogue

@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. – Rescind

Answer 6

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.

Maximilianus

But this requires extra space. The question has the constraint that this needs to be done in-place. – Interdenominational

Um, no. Aside from local variables, this does not. – Maximilianus

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

Buffalo

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);
}

Bombard

Answer 9

***I am giving this solution in Java***

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class MinimumSwapRequiredBTintoBST {
    //Node of binary tree
    public static class Node{
        int data;
        Node left;
        Node right;
        public Node(int data){
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
    public static void main(String []arg){
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.print("Tree traverasl i.e inorder traversal :");
        inorder(root);
        System.out.println(" ");
        MinimumSwapRequiredBTintoBST bst = new MinimumSwapRequiredBTintoBST();
        bst.convertBTBST(root);
    }

    private static void inorder(Node root) {
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.data + "  ");
        inorder(root.right);

    }

   static Node root;
    int[] treeArray;
    int index = 0;

// convert binary tree to binary search tree
    public void convertBTBST(Node node){
        int treeSize = elementsOfTree(node);
        treeArray = new int[treeSize];
        convertBtToArray(node);
        // Sort Array ,Count number of swap

        int minSwap = minimumswap(treeArray);
        System.out.println("Minmum swap required to form BT to BST :" +minSwap);
    }

    private static int minimumswap(int[] arr) {
        int n =arr.length;
        // Create two arrays and use as pairs where first
        // is element and secount array as position of first element
        ArrayList<Pair<Integer, Integer>> arrpos =
            new ArrayList<Pair<Integer, Integer>>();
        // Assign the value
        for(int i =0;i<n;i++)
        {
            arrpos.add(new Pair<Integer, Integer>(arr[i],i));
        }
// Sort the array by array element values to get right
//position of every element as the elements of secound array

        arrpos.sort(new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                return o1.getKey()-o2.getKey();
            }
        });
// To keep track of visited elements .Initially all elements as not visited so put them as false
        int ans = 0;
        boolean []visited = new boolean[n];
        Arrays.fill(visited, false);
        // Traverse array elements
        for(int i =0;i<n;i++){
            // Already swapped and corrected or already present at correct pos
            if(visited[i] || arrpos.get(i).getValue() == i)
                continue;
            // Find out the number of nodes in this cycle and add in ans
            int cycle_size = 0;
            int j =i;
            while(!visited[j]){
                visited[j] = true;
                j = arrpos.get(j).getValue();
                cycle_size++;
            }
            if(cycle_size>0){
                ans += cycle_size-1;
            }
        }
        return ans;
    }

    private void convertBtToArray(Node node) {
        // Check whether tree is empty or not.
        if (root == null) {
            System.out.println("Tree is empty:");
            return;
        }
    else{
        if(node.left != null) {
         convertBtToArray(node.left);}
            treeArray[index] = node.data;
            index++;
            if(node.right != null){
                convertBtToArray(node.right);
            }

        }
    }
    private int elementsOfTree(Node node) {
        int height = 0;
        if(node == null) return 0;
        else{
            height = elementsOfTree(node.left )+ elementsOfTree(node.right)+1;
        }
        return height;
    }


}

Albin

Answer 10

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.

Thaxton

Answer 11

heap sort the tree.. nlogn complexity..

Sectionalize