// Two nodes in the BST's swapped, correct the BST.
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node * left, * right;
} ;
// A utility function to swap two integers
void swap( int * a, int * b )
{
int t = * a;
* a = * b;
* b = t;
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode( int data)
{
struct node
* node
= ( struct node
* ) malloc ( sizeof ( struct node
) ) ; node-> data = data;
node-> left = NULL;
node-> right = NULL;
return ( node) ;
}
// This function does inorder traversal to find out the two swapped nodes.
// It sets three pointers, first, middle and last. If the swapped nodes are
// adjacent to each other, then first and middle contain the resultant nodes
// Else, first and last contain the resultant nodes
void correctBSTUtil( struct node* root, struct node** first,
struct node** middle, struct node** last,
struct node** prev )
{
if ( root )
{
// Recur for the left subtree
correctBSTUtil( root-> left, first, middle, last, prev ) ;
// If this node is smaller than the previous node, it's violating
// the BST rule.
if ( * prev && root-> data < ( * prev) -> data)
{
// If this is first violation, mark these two nodes as
// 'first' and 'middle'
if ( !* first )
{
* first = * prev;
* middle = root;
}
// If this is second violation, mark this node as last
else
* last = root;
}
// Mark this node as previous
* prev = root;
// Recur for the right subtree
correctBSTUtil( root-> right, first, middle, last, prev ) ;
}
}
// A function to fix a given BST where two nodes are swapped. This
// function uses correctBSTUtil() to find out two nodes and swaps the
// nodes to fix the BST
void correctBST( struct node* root )
{
// Initialize pointers needed for correctBSTUtil()
struct node * first, * middle, * last, * prev;
first = middle = last = prev = NULL;
// Set the poiters to find out two nodes
correctBSTUtil( root, & first, & middle, & last, & prev ) ;
// Fix (or correct) the tree
if ( first && last )
swap( & ( first-> data) , & ( last-> data) ) ;
else if ( first && middle ) // Adjacent nodes swapped
swap( & ( first-> data) , & ( middle-> data) ) ;
// else nodes have not been swapped, passed tree is really BST.
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder( struct node* node)
{
if ( node == NULL)
return ;
/* first recur on left child */
printInorder( node-> left) ;
/* then print the data of node */
/* now recur on right child */
printInorder( node-> right) ;
}
void insertBST( struct node** root, int data )
{
if ( !* root )
* root = newNode( data ) ;
else if ( data < ( * root) -> data )
insertBST( & ( ( * root) -> left ) , data ) ;
else
insertBST( & ( ( * root) -> right ) , data ) ;
}
struct node* searchBST( struct node* root, int data )
{
if ( ! root )
return NULL;
if ( root-> data == data )
return root;
else if ( data < root-> data )
return searchBST( root-> left, data ) ;
return searchBST( root-> right, data ) ;
}
void testCase( int arr[ ] , int size, struct node* root )
{
int d1, d2, i;
for ( i = 0 ; i < 10 ; ++ i )
{
printf ( "\n \n Test case #%d\n " , i
) ;
//Generate two nodes randomly to swap, then the program corrects it. :)
d1
= arr
[ rand ( ) % size
] ; d2
= arr
[ rand ( ) % size
] ;
struct node* t1 = searchBST( root, d1 ) ;
struct node* t2 = searchBST( root, d2 ) ;
if ( t1 && t2 ) // both nodes exist
{
printf ( "After swapping the nodes %d and %d\n " , d1
, d2
) ;
swap( & ( t1-> data) , & ( t2-> data) ) ;
printInorder( root ) ;
printf ( "\n After correcting the BST\n " ) ;
correctBST( root ) ;
printInorder( root ) ;
}
}
}
int main( )
{
struct node* root = NULL;
int arr[ ] = { 10 , 5 , 15 , 3 , 7 , 8 , 20 , 25 } ;
int i, size = sizeof ( arr ) / sizeof ( * arr ) ;
for ( i = 0 ; i < size; ++ i )
insertBST( & root, arr[ i] ) ;
printInorder( root ) ;
testCase( arr, size, root ) ;
return 0 ;
}
Ly8gVHdvIG5vZGVzIGluIHRoZSBCU1QncyBzd2FwcGVkLCBjb3JyZWN0IHRoZSBCU1QuCiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CgovKiBBIGJpbmFyeSB0cmVlIG5vZGUgaGFzIGRhdGEsIHBvaW50ZXIgdG8gbGVmdCBjaGlsZAogICBhbmQgYSBwb2ludGVyIHRvIHJpZ2h0IGNoaWxkICovCnN0cnVjdCBub2RlCnsKICAgIGludCBkYXRhOwogICAgc3RydWN0IG5vZGUgKmxlZnQsICpyaWdodDsKfTsKCi8vIEEgdXRpbGl0eSBmdW5jdGlvbiB0byBzd2FwIHR3byBpbnRlZ2Vycwp2b2lkIHN3YXAoIGludCogYSwgaW50KiBiICkKewogICAgaW50IHQgPSAqYTsKICAgICphID0gKmI7CiAgICAqYiA9IHQ7Cn0KCi8qIEhlbHBlciBmdW5jdGlvbiB0aGF0IGFsbG9jYXRlcyBhIG5ldyBub2RlIHdpdGggdGhlCiAgIGdpdmVuIGRhdGEgYW5kIE5VTEwgbGVmdCBhbmQgcmlnaHQgcG9pbnRlcnMuICovCnN0cnVjdCBub2RlKiBuZXdOb2RlKGludCBkYXRhKQp7CiAgICBzdHJ1Y3Qgbm9kZSogbm9kZSA9IChzdHJ1Y3Qgbm9kZSAqKW1hbGxvYyhzaXplb2Yoc3RydWN0IG5vZGUpKTsKICAgIG5vZGUtPmRhdGEgPSBkYXRhOwogICAgbm9kZS0+bGVmdCA9IE5VTEw7CiAgICBub2RlLT5yaWdodCA9IE5VTEw7CiAgICByZXR1cm4obm9kZSk7Cn0KCi8vIFRoaXMgZnVuY3Rpb24gZG9lcyBpbm9yZGVyIHRyYXZlcnNhbCB0byBmaW5kIG91dCB0aGUgdHdvIHN3YXBwZWQgbm9kZXMuCi8vIEl0IHNldHMgdGhyZWUgcG9pbnRlcnMsIGZpcnN0LCBtaWRkbGUgYW5kIGxhc3QuICBJZiB0aGUgc3dhcHBlZCBub2RlcyBhcmUKLy8gYWRqYWNlbnQgdG8gZWFjaCBvdGhlciwgdGhlbiBmaXJzdCBhbmQgbWlkZGxlIGNvbnRhaW4gdGhlIHJlc3VsdGFudCBub2RlcwovLyBFbHNlLCBmaXJzdCBhbmQgbGFzdCBjb250YWluIHRoZSByZXN1bHRhbnQgbm9kZXMKdm9pZCBjb3JyZWN0QlNUVXRpbCggc3RydWN0IG5vZGUqIHJvb3QsIHN0cnVjdCBub2RlKiogZmlyc3QsCiAgICAgICAgICAgICAgICAgICAgIHN0cnVjdCBub2RlKiogbWlkZGxlLCBzdHJ1Y3Qgbm9kZSoqIGxhc3QsCiAgICAgICAgICAgICAgICAgICAgIHN0cnVjdCBub2RlKiogcHJldiApCnsKICAgIGlmKCByb290ICkKICAgIHsKICAgICAgICAvLyBSZWN1ciBmb3IgdGhlIGxlZnQgc3VidHJlZQogICAgICAgIGNvcnJlY3RCU1RVdGlsKCByb290LT5sZWZ0LCBmaXJzdCwgbWlkZGxlLCBsYXN0LCBwcmV2ICk7CgogICAgICAgIC8vIElmIHRoaXMgbm9kZSBpcyBzbWFsbGVyIHRoYW4gdGhlIHByZXZpb3VzIG5vZGUsIGl0J3MgdmlvbGF0aW5nCiAgICAgICAgLy8gdGhlIEJTVCBydWxlLgogICAgICAgIGlmICgqcHJldiAmJiByb290LT5kYXRhIDwgKCpwcmV2KS0+ZGF0YSkKICAgICAgICB7CiAgICAgICAgICAgIC8vIElmIHRoaXMgaXMgZmlyc3QgdmlvbGF0aW9uLCBtYXJrIHRoZXNlIHR3byBub2RlcyBhcwogICAgICAgICAgICAvLyAnZmlyc3QnIGFuZCAnbWlkZGxlJwogICAgICAgICAgICBpZiAoICEqZmlyc3QgKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAqZmlyc3QgPSAqcHJldjsKICAgICAgICAgICAgICAgICptaWRkbGUgPSByb290OwogICAgICAgICAgICB9CgogICAgICAgICAgICAvLyBJZiB0aGlzIGlzIHNlY29uZCB2aW9sYXRpb24sIG1hcmsgdGhpcyBub2RlIGFzIGxhc3QKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgKmxhc3QgPSByb290OwogICAgICAgIH0KCiAgICAgICAgLy8gTWFyayB0aGlzIG5vZGUgYXMgcHJldmlvdXMKICAgICAgICAqcHJldiA9IHJvb3Q7CgogICAgICAgIC8vIFJlY3VyIGZvciB0aGUgcmlnaHQgc3VidHJlZQogICAgICAgIGNvcnJlY3RCU1RVdGlsKCByb290LT5yaWdodCwgZmlyc3QsIG1pZGRsZSwgbGFzdCwgcHJldiApOwogICAgfQp9CgovLyBBIGZ1bmN0aW9uIHRvIGZpeCBhIGdpdmVuIEJTVCB3aGVyZSB0d28gbm9kZXMgYXJlIHN3YXBwZWQuICBUaGlzCi8vIGZ1bmN0aW9uIHVzZXMgY29ycmVjdEJTVFV0aWwoKSB0byBmaW5kIG91dCB0d28gbm9kZXMgYW5kIHN3YXBzIHRoZQovLyBub2RlcyB0byBmaXggdGhlIEJTVAp2b2lkIGNvcnJlY3RCU1QoIHN0cnVjdCBub2RlKiByb290ICkKewogICAgLy8gSW5pdGlhbGl6ZSBwb2ludGVycyBuZWVkZWQgZm9yIGNvcnJlY3RCU1RVdGlsKCkKICAgIHN0cnVjdCBub2RlICpmaXJzdCwgKm1pZGRsZSwgKmxhc3QsICpwcmV2OwogICAgZmlyc3QgPSBtaWRkbGUgPSBsYXN0ID0gcHJldiA9IE5VTEw7CgogICAgLy8gU2V0IHRoZSBwb2l0ZXJzIHRvIGZpbmQgb3V0IHR3byBub2RlcwogICAgY29ycmVjdEJTVFV0aWwoIHJvb3QsICZmaXJzdCwgJm1pZGRsZSwgJmxhc3QsICZwcmV2ICk7CgogICAgLy8gRml4IChvciBjb3JyZWN0KSB0aGUgdHJlZQogICAgaWYoIGZpcnN0ICYmIGxhc3QgKQogICAgICAgIHN3YXAoICYoZmlyc3QtPmRhdGEpLCAmKGxhc3QtPmRhdGEpICk7CiAgICBlbHNlIGlmKCBmaXJzdCAmJiBtaWRkbGUgKSAvLyBBZGphY2VudCBub2RlcyBzd2FwcGVkCiAgICAgICAgc3dhcCggJihmaXJzdC0+ZGF0YSksICYobWlkZGxlLT5kYXRhKSApOwoKICAgIC8vIGVsc2Ugbm9kZXMgaGF2ZSBub3QgYmVlbiBzd2FwcGVkLCBwYXNzZWQgdHJlZSBpcyByZWFsbHkgQlNULgp9CgovKiBHaXZlbiBhIGJpbmFyeSB0cmVlLCBwcmludCBpdHMgbm9kZXMgaW4gaW5vcmRlciovCnZvaWQgcHJpbnRJbm9yZGVyKHN0cnVjdCBub2RlKiBub2RlKQp7CiAgICBpZiAobm9kZSA9PSBOVUxMKQogICAgICAgIHJldHVybjsKCiAgICAvKiBmaXJzdCByZWN1ciBvbiBsZWZ0IGNoaWxkICovCiAgICBwcmludElub3JkZXIobm9kZS0+bGVmdCk7CgogICAgLyogdGhlbiBwcmludCB0aGUgZGF0YSBvZiBub2RlICovCiAgICBwcmludGYoIiVkICIsIG5vZGUtPmRhdGEpOwoKICAgIC8qIG5vdyByZWN1ciBvbiByaWdodCBjaGlsZCAqLwogICAgcHJpbnRJbm9yZGVyKG5vZGUtPnJpZ2h0KTsKfQoKdm9pZCBpbnNlcnRCU1QoIHN0cnVjdCBub2RlKiogcm9vdCwgaW50IGRhdGEgKQp7CiAgICBpZiggISpyb290ICkKICAgICAgICAqcm9vdCA9IG5ld05vZGUoIGRhdGEgKTsKICAgIGVsc2UgaWYoIGRhdGEgPCAoKnJvb3QpLT5kYXRhICkKICAgICAgICBpbnNlcnRCU1QoICYoICgqcm9vdCktPmxlZnQgKSwgZGF0YSApOwogICAgZWxzZQogICAgICAgIGluc2VydEJTVCggJiggKCpyb290KS0+cmlnaHQgKSwgZGF0YSApOwp9CgpzdHJ1Y3Qgbm9kZSogc2VhcmNoQlNUKCBzdHJ1Y3Qgbm9kZSogcm9vdCwgaW50IGRhdGEgKQp7CiAgICBpZiggIXJvb3QgKQogICAgICAgIHJldHVybiBOVUxMOwogICAgaWYoIHJvb3QtPmRhdGEgPT0gZGF0YSApCiAgICAgICAgcmV0dXJuIHJvb3Q7CiAgICBlbHNlIGlmKCBkYXRhIDwgcm9vdC0+ZGF0YSApCiAgICAgICAgcmV0dXJuIHNlYXJjaEJTVCggcm9vdC0+bGVmdCwgZGF0YSApOwogICAgcmV0dXJuIHNlYXJjaEJTVCggcm9vdC0+cmlnaHQsIGRhdGEgKTsKfQoKCnZvaWQgdGVzdENhc2UoIGludCBhcnJbXSwgaW50IHNpemUsIHN0cnVjdCBub2RlKiByb290ICkKewogICAgaW50IGQxLCBkMiwgaTsKCiAgICBmb3IoIGkgPSAwOyBpIDwgMTA7ICsraSApCiAgICB7CiAgICAgICAgcHJpbnRmKCAiXG5cblRlc3QgY2FzZSAjJWRcbiIsIGkgKTsKCiAgICAgICAgLy9HZW5lcmF0ZSB0d28gbm9kZXMgcmFuZG9tbHkgdG8gc3dhcCwgdGhlbiB0aGUgcHJvZ3JhbSBjb3JyZWN0cyBpdC4gOikKICAgICAgICBkMSA9IGFyclsgcmFuZCgpICUgc2l6ZSBdOwogICAgICAgIGQyID0gYXJyWyByYW5kKCkgJSBzaXplIF07CgogICAgICAgIHN0cnVjdCBub2RlKiB0MSA9IHNlYXJjaEJTVCggcm9vdCwgZDEgKTsKICAgICAgICBzdHJ1Y3Qgbm9kZSogdDIgPSBzZWFyY2hCU1QoIHJvb3QsIGQyICk7CgogICAgICAgIGlmKCB0MSAmJiB0MiApIC8vIGJvdGggbm9kZXMgZXhpc3QKICAgICAgICB7CiAgICAgICAgICAgIHByaW50ZiggIkFmdGVyIHN3YXBwaW5nIHRoZSBub2RlcyAlZCBhbmQgJWRcbiIsZDEsIGQyICApOwoKICAgICAgICAgICAgc3dhcCggJih0MS0+ZGF0YSksICYodDItPmRhdGEpICk7CiAgICAgICAgICAgIHByaW50SW5vcmRlciggcm9vdCApOwoKICAgICAgICAgICAgcHJpbnRmKCAiXG5BZnRlciBjb3JyZWN0aW5nIHRoZSBCU1RcbiIgKTsKCiAgICAgICAgICAgIGNvcnJlY3RCU1QoIHJvb3QgKTsKICAgICAgICAgICAgcHJpbnRJbm9yZGVyKCByb290ICk7CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIHN0cnVjdCBub2RlKiByb290ID0gTlVMTDsKCiAgICBpbnQgYXJyW10gPSB7IDEwLCA1LCAxNSwgMywgNywgOCwgMjAsIDI1IH07CgogICAgaW50IGksIHNpemUgPSBzaXplb2YoIGFyciApIC8gc2l6ZW9mKCAqYXJyICk7CgogICAgZm9yKCBpID0gMDsgaSA8IHNpemU7ICsraSApCiAgICAgICAgaW5zZXJ0QlNUKCAmcm9vdCwgYXJyW2ldICk7CgogICAgcHJpbnRmKCAiT3JpZ2luYWwgdHJlZVxuIik7CiAgICBwcmludElub3JkZXIoIHJvb3QgKTsKCiAgICB0ZXN0Q2FzZSggYXJyLCBzaXplLCByb290ICk7CgogICAgcmV0dXJuIDA7Cn0K