Amazon Interview Question
Software Engineer / Developerspsudo 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)){}
}
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;
}
}
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)
}
1) create a doubly linked list from binary tree - inplace
- cougar_Cs October 17, 20082) sort the list
3) create a binary search tree from the sorted list