I prepare one greedy algorithm but restriction that balancing the tree is not guaranteed.
note that i used double linkedlist because of left and right childs named it as node.
take your input in array A,
int highest_lessthan_of_n;
int lowest_graterthan_of_n;
int lessthan_updated_index_of_n;
int graterthan_updated_index_of_n;
B ----> is a list which indicates, inserted nodes in BST, list property is nodes added as linked list at the end
for each A[i]
n=new node with value of A[i];
if BST is empty
{
insert a node in BST with value of A[i];
add node into the list B;
return;
}
else
{
highest_lessthan_of_n = + Infinity ;
lowest_graterthan_of_n = - Infinity ;
lessthan_updated_index_of_n = -1 ; ----> -1 indicting not updated
graterthan_updated_index_of_n = -1 ;
for each B[i]
{
if( n.value > B[i] )
{
if ( highest_lessthan_of_n < B[i] )
{
highest_lessthan_of_n = B[i];
lessthan_updated_index_of_n = i ;
}
}
if( n.value < B[i] )
{
if ( lowest_graterthan_of_n > B[i] )
{
lowest_graterthan_of_n = B[i];
graterthan_updated_index_of_n = i ;
}
}
}
if( lessthan_updated_index_of_n > graterthan_updated_index_of_n ) -----> lessthan_updated_index_of_n is recently updated
add new node as right of the lessthan_updated_index_of_n;
if( graterthan_updated_index_of_n > lessthan_updated_index_of_n ) -----> graterthan_updated_index_of_n is recently updated
add new node as left of the graterthan_updated_index_of_n;
add node into the list B;
return ;
}