Binary Tree to Binary Search Tree Conversion

PROBLEM :

Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.

Examples.

Example 1
Input:
          10
         /  \
        2    7
       / \
      8   4
Output:
          8
         /  \
        4    10
       / \
      2   7


Example 2
Input:
          10
         /  \
        30   15
       /      \
      20       5
Output:
          15
         /  \
       10    20
       /      \
      5        30

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------


/*
typedef struct BST
{
int info ;
struct BST *left ;
struct BST *right ;
}tree ;                                 */

int size_tree(tree* ) ;
void inorder_array_fill(tree* ,int [],int *) ;
void sort_array(int [],int ) ;
void inorder_tree_fill(tree **,int [],int *) ;


tree * BT_to_BST(tree *root)
{
int s ;
s=size_tree(root) ;

int array[s],i=0 ;
inorder_array_fill(root,array,&i) ;

sort_array(array,s) ;

i=0 ;
inorder_tree_fill(&root,array,&i) ;
return root ;
}    

int size_tree(tree* root)
{
if(root==NULL)
return 0 ;

return ((size_tree(root->left))+(size_tree(root->right))+1) ;
}

void inorder_array_fill(tree* root,int a[],int *s)
{
    if(root==NULL)
        return  ;
     
    inorder_array_fill(root->left,a,&(*s)) ;
    a[(*s)++]=root->info ;
    inorder_array_fill(root->right,a,&(*s)) ;
 
}    

// for sorting we can also use heap sort or mearge sort to reduce the complexity

void sort_array(int a[],int no)
{
int i,j,temp ;
for(i=0;i<no-1;i++)
{
for(j=0;j<no-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j+1] ;
a[j+1]=a[j] ;
a[j]=temp ;
}
}
}
}

void inorder_tree_fill(tree **root,int a[],int *i)
{
if((*root)==NULL)
return ;

inorder_tree_fill(&((*root)->left),a,&(*i)) ;
(*root)->info=a[(*i)++] ;
inorder_tree_fill(&((*root)->right),a,&(*i)) ;
}

---------------------------------------------------------------------------------