Advertisement
imashutosh51

Fixing Two nodes of a BST

Aug 4th, 2022
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. /*
  2. Logic:
  3. Inorder of BST is always sorted.
  4. If only one node will be swapped in a BST then there is only two possibility:
  5.  
  6. case1:
  7. eg Inorder: 3 25 7 8 10 15 20 5 swapped nodes(ie. 25, 5) are not adjacent
  8. here the current node ie. 7  is lesser than previous node,ie. 25 so make left=25,middle=7
  9. and again 5 is lesse than 20 so make left=5.
  10. if there is left,middle and right then swap(left,right);
  11.  
  12. case 2:swapped nodes are adjacent
  13. eg. 3 5 8 7 10 15 20 25
  14. swapped node(ie. 8,7)
  15. using previous case left=8 and middle=7.
  16. no voilation or sorted order again,so no right node so,swap(left,middle)
  17.  
  18. */
  19. Node *l=NULL,*m=NULL,*r=NULL,*p=NULL;  //l=left,m=middle,r=right,p=previous
  20. void inorder(Node *root){
  21.     if(root){
  22.         inorder(root->left);
  23.         if(p){
  24.             if(root->data<p->data && !l){
  25.                 l=p;
  26.                 m=root;
  27.             }
  28.             else if(root->data<p->data && l){
  29.                 r=root;
  30.             }
  31.         }
  32.         p=root;
  33.         inorder(root->right);
  34.     }
  35. }
  36. void fun(Node *root){
  37.     if(root){
  38.         fun(root->left);
  39.         cout<<root->data<<" ";
  40.         fun(root->right);
  41.     }
  42. }
  43. class Solution {
  44.   public:
  45.     void correctBST( struct Node* root ){
  46.         l=NULL;m=NULL;r=NULL;p=NULL;
  47.         inorder(root);
  48.         if(r){
  49.             int temp=l->data;
  50.             l->data=r->data;
  51.             r->data=temp;
  52.         }
  53.         else{
  54.             int temp=l->data;
  55.             l->data=m->data;
  56.             m->data=temp;
  57.         }
  58.     }
  59. };
  60.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement