CareerCup

1) create a doubly linked list from binary tree - inplace
2) sort the list
3) create a binary search tree from the sorted list

do heapsort

psudo code:
bool sortTree(Tree* node)
{
static bool swapped=0;
Tree* left=node->left;bool sortTree(Tree* node)
{
bool swapped=0;
Tree* left=node->left;
Tree* right=node->right;

if(!node) return 0;

if(left)
{ if(left->data>node->data)
{swap(left->data,node->data);
swapped=1;}

}

if(right)
{ if(right->data<node->data)
{swap(right->data,node->data);
swapped=1;}
}

if(left&&right)
{ if(left->data>right->data)
{swap(left->data,right->data);
swapped=1;}
}


swapped=swapped||sort(left)||sort(right);

return swapped;

}

void doTreeSort(Tree* root)
{
while(sortTree(root)){}

}


Tree* right=node->right;

if(!node) return 0;
while(swapped)
{

if(left)
{ if(left->data>node->data)
{swap(left->data,node->data);
swapped=1;}

}

if(right)
{ if(right->data<node->data)
{swap(right->data,node->data);
swapped=1;}
}

if(left&&right)
{ if(left->data>right->data)
{swap(left->data,right->data);
swapped=1;}
}

swapped=swapped||sort(left)||sort(right);


}

}

corrected:

bool sortTree(Tree* node)
{
bool swapped=0;
Tree* left=node->left;
Tree* right=node->right;

if(!node) return 0;

if(left)
{ if(left->data>node->data)
{swap(left->data,node->data);
swapped=1;}

}

if(right)
{ if(right->data<node->data)
{swap(right->data,node->data);
swapped=1;}
}

if(left&&right)
{ if(left->data>right->data)
{swap(left->data,right->data);
swapped=1;}
}


swapped=swapped||sort(left)||sort(right);

return swapped;

}

void doTreeSort(Tree* root)
{
while(sortTree(root)){}

}

heap sort is the best answer as it's "in place"...

the above solution keeps call sortTree once if he root, its left child, & right child are not in heap order, then will quit. Becayse || operator is used sort(left), sort(right) will not occur as swapped == 1.

Also, seems like this is intended to produce a heap, not a BST. The question is to create a BST.

Is there an algorithm that converts a given tree into BST inplace ?

hi ,

I think the following is the high level logic recursive for inplace conversion

func( Node node)
{
if(node==null)
return;
func(node->left);
func(node->right);
if(node->right==null && node->left==null)
return;
else if(node->right==null)
{
int k= larger (node.data and node->left.data)
if(k!=node.data)
{
node->left.data =node.data;
node.data=k;
}
}
else if(node->left==null)
{
int k= smaller(node.data and node->right.data)
if(k!=node.data)
{
node->right.data =node.data;
node.data=k;
}
}
else
{
int sm=smaller(node.data,node->left.data,node->right.data);
int max=larger(node.data,node->left.data,node->right.data);
int third=The element that is between the sm and max;
node.data=third;
node->left.data=sm;
node->right.data=max;
}
}

no proper answer so far !
any one out there with a logically correct and working answer ???

We don't need to sort the tree because we just need a Binary search tree.
Hence for each node, make sure that the left child is less than the current node and right child is greater than current node. Repeat for every node.

ConvertBinarySearchTree(NodeStruct *Node)
{
....temp1 = Node->left
....temp2 = Node->right
....if(Node->value < temp1->value) exchange(Node->value, temp1->value)
....if(Node->value > temp2->value) exchange(Node->value, temp2->value)
....ConvertBinarySearchTree(Node->left)
....ConvertBinarySearchTree(Node->right)
}

That wouldnt be a BST, since it doesnt guarantee that all elements in left sub-tree is less than or equal to the root element.