Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
Use modified Inorder traversal.
correctBST(root)
{
static Node* temp1,*temp2,*prev;
static int found;
if(root)
{
correctBST(root->left);
if(!temp1 && prev && root->data<prev->data)
{
temp1=prev;
temp2=root;
}
else if(prev && root->data<prev->data)
temp2=root;
else if(temp1 && temp2 && !found)
{
swap(&(temp1->data),&(temp2->data));
found=1;
return;
}
prev=root;
correctBST(root->right);
}
}
Could you explain the value of temp1 here?
if(!temp1 && prev && root->data<prev->data)
It is not initialized
f(!temp1 && prev && root->data<prev->data)
pre is uninitilized pointer.....can u kindly modify this
Wonderful approach, few corrections and this work like a charm.
correctBST(root)
{
static Node* temp1,*temp2,*prev;
static int found;
if(found) return;
if(root)
{
correctBST(root->left);
if(!temp1 && prev && root->data<prev->data)
temp1=prev;
else if(!temp2 && prev && root->data<prev->data)
temp2=root;
if(temp1 && temp2 && !found)
{
swap(&(temp1->data),&(temp2->data));
found=1;
return;
}
prev=root;
correctBST(root->right);
}
}
I think there is some problem with the code if you take the example
25
15 35
10 18 30 40
Now if you exchange 35 with 10 then the resultant tree would be
25
15 10
35 18 30 40
The given algo won't work for this example.
@Abhishank Sahu, the algo is working well with the inut set given by you. Can you provide the link where it didn't give the correct output?
This is not working! This will find the 1st node correctly, but will not always find the 2nd node
For instance consider this
5
/ \
4 6
/ \ \
1 2 7
temp1 will point to 2, and temp2 will point to nowhere!
Check carefully!
There is a minor problem in the code . this doesnt work when the left child of any left subtree has been swapped. For example:
5
/ \
4 6
/ \ \
7 2 1
the code posted by AA it still doesnt work. A slight modification to AA's code will rectify it:
correctBST(root)
{
static Node* temp1,*temp2,*prev;
static int found;
if(found) return;
if(root)
{
correctBST(root->left);
//to handle the case when a left child of a left subtree is swapped
if(!prev)
prev = root -> left
if(!temp1 && prev && root->data<prev->data)
temp1=prev;
else if(!temp2 && prev && root->data<prev->data)
temp2=root;
if(temp1 && temp2 && !found)
{
swap(&(temp1->data),&(temp2->data));
found=1;
return;
}
prev=root;
correctBST(root->right);
}
}
// Correct a BST where two nodes are swapped
void GetDeviants(Node* root, int nMin, int nMax, __out std::vector<Node*>* prgDeviants)
{
if (nullptr == root)
{
return;
}
if (nullptr != root->left)
{
GetDeviants(root->left, nMin, root->val, prgDeviants);
}
if (nullptr != root->right)
{
GetDeviants(root->right, root->val+1, nMax, prgDeviants);
}
if ((root->val < nMin) || (root->val > nMax))
{
prgDeviants->push_back(root);
}
}
void CorrectBST(Node* root)
{
std::vector<Node*> rgDeviants;
rgDeviants.reserve(2);
GetDeviants(root, -INFINITY, INFINITY, &rgDeviants);
ASSERT(2 == rgDeviants.size());
std::swap(&(rgDeviants[0]->val), &(rgDeviants[1]->val));
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node Tree;
Tree *new_node(int data)
{
Tree *node = (Tree *)malloc(sizeof(Tree));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
void make_tree(Tree **root,int data) // constructing tree
{
if(*root==NULL)
{
*root = new_node(data);
}
else
{
if(data>(*root)->data)
{
make_tree(&(*root)->right,data);
}
else
{
make_tree(&(*root)->left,data);
}
}
}
int arr[5]; // storing inorder traversal into global array so it can reflect in our main
void inorder(Tree *root)
{
static int i=0;
if(root==NULL)
return;
inorder(root->left);
arr[i++]=root->data;
cout<<root->data<<"\t";
inorder(root->right);
}
int main()
{
Tree *head=new_node(5); // making tree as per given condition
head->left=new_node(3);
head->right=new_node(4);
head->left->left=new_node(2);
head->left->right=new_node(6);
inorder(head);
cout<<endl;
int count=0,index1,index2;
for(int k=0;k<4;k++) // finding position of swap indexes in an array
{
if(arr[k]>arr[k+1] && count==0)
{ index1=k; count++;}
if(arr[k]>arr[k+1] && count==1)
index2=k;
}
int temp=arr[index1]; // swap those values
arr[index1]=arr[index2];
arr[index2]=temp;
head=NULL; // again reconstructing
for(int k=0;k<5;k++)
make_tree(&head,arr[k]);
inorder(head);
getchar();
return 0;
}
Traverse the whole tree to find the two parents(victim) where the lft child> rt child. Having the pntr to this parent, swap the two child(wrong one). Hope the idea works..
let take below case
55
30 50
here 55 & 50 are swapped, in this case there is no childs for 50... here does your logic works?
inorder traversal of bst. Check if it's sorted. if not, the two nodes which are not fulfilling the criteria swap them
- Anonymous July 28, 2012