(106). 28.11. RECOVER BINARY SEARCH TREE - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

#include <bits/stdc++.h> using namespace std;

struct Node{ int data; Node *left , *right;

Node(int val){
	data = val;
	left = NULL;
	right = NULL;
}

};

//swap function void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; }

//calculate pointers function void calcPointers(Node* root, Node** first, Node** mid, Node** last, Node** prev){ if(root == NULL){ return; } calcPointers(root->left, first, mid, last, prev);

if(*prev && root->data < (*prev)->data){
	if(!*first){
		*first = *prev;
		*mid = root;
	}
	else{
		*last = root;
	}
}
*prev = root;
calcPointers(root->right, first, mid, last, prev);	

}

//restore/recovery BST Function void restoreBST(Node* root){ Node* first, *mid, *last, *prev; first = NULL; mid = NULL; last = NULL; prev = NULL;

calcPointers(root, &first, &mid, &last, &prev);


//case 1
if(first && last){
	swap(&(first->data), &(last->data));
}
else if(first && mid){
	swap(&(first->data), &(mid->data));
}

}

//inorder function void inorder(Node* root){ if(root == NULL){ return; }

inorder(root->left);
cout << root->data <<" ";
inorder(root->right);

}

int main(){ /* 6 /
9 3 / \
1 4 13 / Node root = new Node(6); root->left = new Node(9); root->right = new Node(3); root->left->left = new Node(1); root->left->right = new Node(4); root->right->right = new Node(13);

cout << "Original BST: ";
inorder(root);
cout << endl;

cout << "Restore BST: ";
restoreBST(root);
inorder(root);
cout << endl; 

return 0;

}

/* OUTPUT: Original BST: 1 9 4 6 3 13 Recover BST: 1 3 4 6 9 13 */