#include <bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *left;
struct Node *right;
Node(int k){
key=k;
left=right=NULL;
}
};
void inorder(Node *root){
if(root!=NULL){
inorder(root->left);
cout<<root->key<<" ";
inorder(root->right);
}
}
Node *prevv=NULL,*first=NULL,*second=NULL;
void fixBST(Node* root)
{
if (root == NULL)
return;
fixBST(root->left);
if(prevv!=NULL && root->key<prevv->key){
if(first==NULL)
first=prevv;
second=root;
}
prevv=root;
fixBST(root->right);
}
int main() {
Node *root = new Node(18);
root->left = new Node(60);
root->right = new Node(70);
root->left->left = new Node(4);
root->right->left = new Node(8);
root->right->right = new Node(80);
inorder(root);
cout<<endl;
fixBST(root);
int temp=first->key;
first->key=second->key;
second->key=temp;
inorder(root);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgTm9kZSAgCnsgCiAgaW50IGtleTsgCiAgc3RydWN0IE5vZGUgKmxlZnQ7CiAgc3RydWN0IE5vZGUgKnJpZ2h0OyAKICBOb2RlKGludCBrKXsKICAgICAga2V5PWs7CiAgICAgIGxlZnQ9cmlnaHQ9TlVMTDsKICB9Cn07Cgp2b2lkIGlub3JkZXIoTm9kZSAqcm9vdCl7CiAgICBpZihyb290IT1OVUxMKXsKICAgICAgICBpbm9yZGVyKHJvb3QtPmxlZnQpOwogICAgICAgIGNvdXQ8PHJvb3QtPmtleTw8IiAiOwogICAgICAgIGlub3JkZXIocm9vdC0+cmlnaHQpOwogICAgfQp9CgpOb2RlICpwcmV2dj1OVUxMLCpmaXJzdD1OVUxMLCpzZWNvbmQ9TlVMTDsKdm9pZCBmaXhCU1QoTm9kZSogcm9vdCkgIAp7ICAKICAgIGlmIChyb290ID09IE5VTEwpICAKICAgICAgICByZXR1cm47ICAKICAgIGZpeEJTVChyb290LT5sZWZ0KTsKICAgIGlmKHByZXZ2IT1OVUxMICYmIHJvb3QtPmtleTxwcmV2di0+a2V5KXsKICAgICAgICBpZihmaXJzdD09TlVMTCkKICAgICAgICAgICAgZmlyc3Q9cHJldnY7CiAgICAgICAgc2Vjb25kPXJvb3Q7CiAgICB9CiAgICBwcmV2dj1yb290OwogICAgCiAgICBmaXhCU1Qocm9vdC0+cmlnaHQpOwp9CgppbnQgbWFpbigpIHsKCQoJTm9kZSAqcm9vdCA9IG5ldyBOb2RlKDE4KTsgIAogICAgcm9vdC0+bGVmdCA9IG5ldyBOb2RlKDYwKTsgIAogICAgcm9vdC0+cmlnaHQgPSBuZXcgTm9kZSg3MCk7ICAKICAgIHJvb3QtPmxlZnQtPmxlZnQgPSBuZXcgTm9kZSg0KTsgIAogICAgcm9vdC0+cmlnaHQtPmxlZnQgPSBuZXcgTm9kZSg4KTsKICAgIHJvb3QtPnJpZ2h0LT5yaWdodCA9IG5ldyBOb2RlKDgwKTsgIAogICAgCiAgICBpbm9yZGVyKHJvb3QpOyAKICAgIGNvdXQ8PGVuZGw7CiAgICBmaXhCU1Qocm9vdCk7CiAgICBpbnQgdGVtcD1maXJzdC0+a2V5OwogICAgZmlyc3QtPmtleT1zZWNvbmQtPmtleTsKICAgIHNlY29uZC0+a2V5PXRlbXA7CiAgICBpbm9yZGVyKHJvb3QpOwogICAgICAgICAgCiAgICByZXR1cm4gMDsgIAoJCn0=