fork 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.  
  33. int fbst(node *root)
  34. {
  35. node *p1=NULL;
  36. node *p2=NULL;
  37. node *t1=root->left;
  38. node *t2=root->right;
  39. if((t1->data<root->data) && (t2->data>root->data))
  40. {
  41. fbst(t1);
  42. fbst(t2);
  43. }
  44. else if((t1->data<root->data) && (t2->data<root->data))
  45. {
  46. fbst(t1);
  47. p2=t2;
  48. }
  49. else if((t1->data>root->data) && (t2->data>root->data))
  50. {
  51. fbst(t2);
  52. p1=t1;
  53. }
  54. else if((t1->data>root->data) && (t2->data<root->data))
  55. {
  56. p2=t2;
  57. p1=t1;
  58. }
  59. swap(&(p1->data),&(p2->data));
  60. }
  61.  
  62. void printInorder(struct node* node)
  63. {
  64.     if (node == NULL)
  65.         return;
  66.     printInorder(node->left);
  67.     printf("%d ", node->data);
  68.     printInorder(node->right);
  69. }
  70.  
  71. /* Driver program to test above functions*/
  72. int main()
  73. {
  74.     /*   6
  75.         /  \
  76.        10    2
  77.       / \   / \
  78.      1   3 7  12
  79.      10 and 2 are swapped
  80.     */
  81.  
  82.     struct node *root = newNode(6);
  83.     root->left        = newNode(10);
  84.     root->right       = newNode(2);
  85.     root->left->left  = newNode(1);
  86.     root->left->right = newNode(3);
  87.     root->right->right = newNode(12);
  88.     root->right->left = newNode(7);
  89.  
  90.     printf("Inorder Traversal of the original tree \n");
  91.     printInorder(root);
  92.  
  93.     fbst(root);
  94.  
  95.     printf("\nInorder Traversal of the fixed tree \n");
  96.     printInorder(root);
  97.  
  98.     return 0;
  99. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder Traversal of the original tree 
1 10 3 6 7 2 12 
Inorder Traversal of the fixed tree 
1 2 3 6 7 10 12
https://ideone.com/joJ8ZX
language:
C++ (gcc 8.3)
created:
6 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!