fork(16) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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
https://ideone.com/uNlPx
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!