## Microsoft Interview Question

Software Engineer / Developers- 0of 0 votes
Two elements of BST are swapped by mistake. You have to restore the tree without changing its structure.

**Country:**India

I too am unwilling to invest time in reading code when I know that statistically speaking 80% of the answers on this site are incorrect

it does not work if root is one of the buggy nodes.

Test with:

3(root)->left=2; 3->right=null

2->left=1(leaf), 2->right=5(leaf)

Here 3 and 5 need to be swapped but the code cannot find 3.

Create a stack and start inserting the nodes of BST in stack in in-order fashion

if elt/node that we are going to insert is larger than stack top, pop the top node and push the elt/node

else push the elt/node

Finally swap the values of first and last nodes in Stack (After the traversal stack will have two elements if adjacent numbers are swapped and stack will have three elements if non-adjacent numbers are swapped)

this is best so far. some optimizations like -:

we can stop early

I.e after finding first anamoly using your method (anamoly is "number whose next number is smaller than the itself", no need of Stack just variable could do).

Now we just have to traverse to find the number's position whose next number is bigger than anamoly number

Don't know if this logic works for all test cases:

1. Find In order traversal of the tree.

2. In the inorder traversal, from left to right, find the first node which is misplaced(A misplaced element is one which is greater than its right element in the inorder matrix).

3. Now taking the element found in step two, traverse inorder array from left to right, and find the first element which is less than the element found in step two.

So the in actual implementation, for step two we traverse tree in order two find the node.

And two find the second node in step three we traverse in reverse inorder.

Example:

Actual tree inorder : 2,5,7,8,10,12,14

Disorder Tree inorder : 2,8,7,5,10,12,14(5,8 are swapped)

In step two we find 8 (As the right element 7 is less than 8)

Now in step three we find 5 which is the first element found which is less than 8.

Correct we if my logic is wrong

Start with inorder traversal, keep a reference of current and old node. The moment you find out-of-order numbers, swap the values.

This method is incorrect because the swapped nodes are not necessarily adjacent in an in-order traversal.

store inorder traversal of tree in an array and sort it ,and again do inorder traversal and insert value from sorted array to tree .

the method posted by PKS may not work.

The two nodes swapped may not be adjacent to each other in inorder traversal. Instead when you find a node that is out of order do a binary search for the correct position of the node and swap with that node.

No, this works. The tree structure won't be changed. After the array is sorted, an in-order traversal of the tree will be done, and the i-th node in the in-oirder traversal will get the i-th value from the array. The problem here is that 1) you are using extra space (no one said you couldn't, but still); 2) sorting is O(NlogN) whereas this problem can be solved in O(N); and 3) even if you realize that you should use insertion sort because the list is almost sorted and end up with an O(N) sort here (since only O(1) elements are out of order), you're still doing 2 tree traversals, writing to an array, and doing an insertion sort when it's possible to solve this problem with just one tree traversal.

void Tree::GetMaxMin(TNode* node,int *cmp,bool flag)

{

if(node == NULL) return;

if(flag)

*cmp = *cmp > node->val?node->val:*cmp;

else

*cmp = *cmp < node->val?node->val:*cmp;

GetMaxMin(node->left,cmp,flag);

GetMaxMin(node->right,cmp,flag);

}

void Tree::swap(TNode* node,int min,int max)

{

if(node==NULL) return;

if(node->val == min || node->val == max)

node->val = node->val==min?max:min;

swap(node->left,min,max);

swap(node->right,min,max);

}

void Tree::BSTNormal(TNode* node)

{

if(node==NULL) return;

int max = node->val;

int min = node->val;

GetMaxMin(node->left,&max,0);

GetMaxMin(node->right,&min,1);

if(min < max)

swap(node,max,min);

else if(node->val <= max)

swap(node,node->val,max);

else if(node->val >= min)

swap(node,node->val,min);

BSTNormal(node->left);

BSTNormal(node->right);

}

tarverse the tree in inorder nd preorder way nd store in two arrays.. now check for the incorrect number in inorderly filled array(as can be easily seen b'coz number must be sorted) and den swap dese two values in both tha arrays i.e. inorder traversed array and preoder traversed array.. and then using two traversal its easy to create the tree with the same structure as that of before..

p.s. two traversal are required just to maintain the structure or else only one can also work.. :)

Assumption: the swapped nodes are breaking the BST features of the tree.

Step 1: Find two BST violated nodes using modified isBST() testing routine. Please check the isBST() method.

Step 2: Swap the content of those two nodes.

This should work. But just swapping the nodes content wouldn't work instead the subtree of faulty node and its children should be considered before swapping the nodes.

This will not work because you cannot always find only two nodes that violate BST rule. Consider the tree below:

8

/ \

5 12

/ \ / \

2 7 10 14

Swapping 8 and 10 gives us:

10

/ \

5 12

/ \ / \

2 7 8 14

Which two violate? 8 and 10? Then how about 12?

The method works. Consider the isBST calls when we are traversing the right sub tree.

assume isBST (Tree, min, max);

For node 12, we get isBST (T, 10, INT_MAX); which is ok for 12

For node 8, we get isBST(T, 10, 12); which is not ok, as 8 < 10 (min). so we set the 2 nodes to be swapped as 8, 10.

In cases, if the swapped nodes belong to left and right subtrees, then isBST will encounter such anomaly twice , and we can simply set the nodes to be swapped as the nodes that caused those anomalies.

```
// Set the swapNodes[0] = swapNodes[1] = -1
if (data < min || data > max)
{
if (swapNodes[0] == -1)
{
swapNodes[0] = data;
swapNodes[1] = data < min ? min : max;
}
else
// We encountered second anomaly in the isBST.
swapNodes[1] = data;
}
```

is it right?? plzzz comment

typedef struct node *NODEPTR;

void tree(NODEPTR root)

{

NODEPTR p=NULL, j=NULL;

if(root==NULL)

return;

else if(root!=NULL && (j==NULL || p==NULL))

{

if( root->left != NULL && root->info < (root->left)->info )

j = root->left;

if( root->right != NULL && root->info >= (root->right)->info )

p = root->right;

tree( root->left );

tree( root->right );

}

swap( j->info , p->info );

}

Do an in order element ...

misplaced element will be 2 elements

[1] one element will be greater than both of it's left and right

[2] 2nd element will be less than both left and right

Swap above 2 elements

- Gautam August 30, 2012