SDE - 1

class Solution
{
Node first= null; // store 1st violated number
Node middle=null; // 1st number adjacent number
Node second=null; // store 2nd violated number
Node prev=new Node(Integer.MIN_VALUE); // use for comparison with it's current root node

public void inorder(Node root){
if(root==null){
return;
}
// itterate left subtree
inorder(root.left);

// checking if previous element is breaking the ascending order sequence
if(prev.data > root.data){

// If this is first violation, mark these two nodes as
// 'first' and 'middle'
if(first == null){
first=prev;
middle=root;
}

// If this is second violation, mark this node as second
else{
second=root;
}
}
// Mark this node as previous, for the comparison purpose
prev=root;
// itterate right subtree
inorder(root.right);
}
//Function to fix a given BST where two nodes are swapped. 
public Node correctBST(Node root)
{
//code here.
inorder(root);
if(second != null){
int temp=first.data;
first.data=second.data;
second.data=temp;
}
else{
int temp=first.data;
first.data=middle.data;
middle.data=temp;
}
return root;
}
}

Node* curr = head;
Node* prev = NULL;
while(curr != NULL){
Node* next = curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
return prev;

Tip 1 : Try to give answer with the real life examples always.
Tip 2 : Give answers in your language and avoid the bookish language