CareerCup

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)

int
buggynode1(node* root,int min,int max)
{
  int left=0;
  int right=0;

  if(root)
    {
      if(root->data<min) return root->data;
      if(root->data>max) return root->data;

      left=buggynode1(root->left,min,root->data);
      if(left) return left;

      right=buggynode1(root->right,root->data,max);
      if(right) return right;
    }
  return 0;
}



int
buggynode2(node* root,int min,int max)
{
  int left=0;
  int right=0;

  if(root)
    {
      if(root->data>max) return root->data;
      if(root->data<min) return root->data;


      right=buggynode2(root->right,root->data,max);
      if(right) return right;

      left=buggynode2(root->left,min,root->data);
      if(left) return left;
    }
  return 0;
}

void
swapBuggy(node* root, int buggy1,int buggy2)
{
  if(root)
    {
      if(root->data==buggy1 || root->data==buggy2)
        {
          root->data=root->data^buggy1^buggy2;
        }
      swapBuggy(root->left,buggy1,buggy2);
      swapBuggy(root->right,buggy1,buggy2);
    }
}

int 
main()
{
  int tmp1=buggynode1(root,INT_MIN,INT_MAX);
  int tmp2=buggynode2(root,INT_MIN,INT_MAX);
 
  swapBuggy(root,tmp1,tmp2)
}

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.

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.

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.

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