fork(15) download
  1. // Two nodes in the BST's swapped, correct the BST.
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. /* A binary tree node has data, pointer to left child
  6.   and a pointer to right child */
  7. struct node
  8. {
  9. int data;
  10. struct node *left, *right;
  11. };
  12.  
  13. // A utility function to swap two integers
  14. void swap( int* a, int* b )
  15. {
  16. int t = *a;
  17. *a = *b;
  18. *b = t;
  19. }
  20.  
  21. /* Helper function that allocates a new node with the
  22.   given data and NULL left and right pointers. */
  23. struct node* newNode(int data)
  24. {
  25. struct node* node = (struct node *)malloc(sizeof(struct node));
  26. node->data = data;
  27. node->left = NULL;
  28. node->right = NULL;
  29. return(node);
  30. }
  31.  
  32. // This function does inorder traversal to find out the two swapped nodes.
  33. // It sets three pointers, first, middle and last. If the swapped nodes are
  34. // adjacent to each other, then first and middle contain the resultant nodes
  35. // Else, first and last contain the resultant nodes
  36. void correctBSTUtil( struct node* root, struct node** first,
  37. struct node** middle, struct node** last,
  38. struct node** prev )
  39. {
  40. if( root )
  41. {
  42. // Recur for the left subtree
  43. correctBSTUtil( root->left, first, middle, last, prev );
  44.  
  45. // If this node is smaller than the previous node, it's violating
  46. // the BST rule.
  47. if (*prev && root->data < (*prev)->data)
  48. {
  49. // If this is first violation, mark these two nodes as
  50. // 'first' and 'middle'
  51. if ( !*first )
  52. {
  53. *first = *prev;
  54. *middle = root;
  55. }
  56.  
  57. // If this is second violation, mark this node as last
  58. else
  59. *last = root;
  60. }
  61.  
  62. // Mark this node as previous
  63. *prev = root;
  64.  
  65. // Recur for the right subtree
  66. correctBSTUtil( root->right, first, middle, last, prev );
  67. }
  68. }
  69.  
  70. // A function to fix a given BST where two nodes are swapped. This
  71. // function uses correctBSTUtil() to find out two nodes and swaps the
  72. // nodes to fix the BST
  73. void correctBST( struct node* root )
  74. {
  75. // Initialize pointers needed for correctBSTUtil()
  76. struct node *first, *middle, *last, *prev;
  77. first = middle = last = prev = NULL;
  78.  
  79. // Set the poiters to find out two nodes
  80. correctBSTUtil( root, &first, &middle, &last, &prev );
  81.  
  82. // Fix (or correct) the tree
  83. if( first && last )
  84. swap( &(first->data), &(last->data) );
  85. else if( first && middle ) // Adjacent nodes swapped
  86. swap( &(first->data), &(middle->data) );
  87.  
  88. // else nodes have not been swapped, passed tree is really BST.
  89. }
  90.  
  91. /* Given a binary tree, print its nodes in inorder*/
  92. void printInorder(struct node* node)
  93. {
  94. if (node == NULL)
  95. return;
  96.  
  97. /* first recur on left child */
  98. printInorder(node->left);
  99.  
  100. /* then print the data of node */
  101. printf("%d ", node->data);
  102.  
  103. /* now recur on right child */
  104. printInorder(node->right);
  105. }
  106.  
  107. void insertBST( struct node** root, int data )
  108. {
  109. if( !*root )
  110. *root = newNode( data );
  111. else if( data < (*root)->data )
  112. insertBST( &( (*root)->left ), data );
  113. else
  114. insertBST( &( (*root)->right ), data );
  115. }
  116.  
  117. struct node* searchBST( struct node* root, int data )
  118. {
  119. if( !root )
  120. return NULL;
  121. if( root->data == data )
  122. return root;
  123. else if( data < root->data )
  124. return searchBST( root->left, data );
  125. return searchBST( root->right, data );
  126. }
  127.  
  128.  
  129. void testCase( int arr[], int size, struct node* root )
  130. {
  131. int d1, d2, i;
  132.  
  133. for( i = 0; i < 10; ++i )
  134. {
  135. printf( "\n\nTest case #%d\n", i );
  136.  
  137. //Generate two nodes randomly to swap, then the program corrects it. :)
  138. d1 = arr[ rand() % size ];
  139. d2 = arr[ rand() % size ];
  140.  
  141. struct node* t1 = searchBST( root, d1 );
  142. struct node* t2 = searchBST( root, d2 );
  143.  
  144. if( t1 && t2 ) // both nodes exist
  145. {
  146. printf( "After swapping the nodes %d and %d\n",d1, d2 );
  147.  
  148. swap( &(t1->data), &(t2->data) );
  149. printInorder( root );
  150.  
  151. printf( "\nAfter correcting the BST\n" );
  152.  
  153. correctBST( root );
  154. printInorder( root );
  155. }
  156. }
  157. }
  158.  
  159. int main()
  160. {
  161. struct node* root = NULL;
  162.  
  163. int arr[] = { 10, 5, 15, 3, 7, 8, 20, 25 };
  164.  
  165. int i, size = sizeof( arr ) / sizeof( *arr );
  166.  
  167. for( i = 0; i < size; ++i )
  168. insertBST( &root, arr[i] );
  169.  
  170. printf( "Original tree\n");
  171. printInorder( root );
  172.  
  173. testCase( arr, size, root );
  174.  
  175. return 0;
  176. }
  177.  
Success #stdin #stdout 0.01s 1808KB
stdin
Standard input is empty
stdout
Original tree
3 5 7 8 10 15 20 25 

Test case #0
After swapping the nodes 25 and 20
3 5 7 8 10 15 25 20 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #1
After swapping the nodes 5 and 3
5 3 7 8 10 15 20 25 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #2
After swapping the nodes 5 and 25
3 25 7 8 10 15 20 5 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #3
After swapping the nodes 15 and 7
3 5 15 8 10 7 20 25 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #4
After swapping the nodes 5 and 8
3 8 7 5 10 15 20 25 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #5
After swapping the nodes 15 and 3
15 5 7 8 10 3 20 25 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #6
After swapping the nodes 15 and 3
15 5 7 8 10 3 20 25 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #7
After swapping the nodes 3 and 20
20 5 7 8 10 15 3 25 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #8
After swapping the nodes 7 and 15
3 5 15 8 10 7 20 25 
After correcting the BST
3 5 7 8 10 15 20 25 

Test case #9
After swapping the nodes 7 and 10
3 5 10 8 7 15 20 25 
After correcting the BST
3 5 7 8 10 15 20 25