#codingexercise

Two of the nodes of a BST are swapped. Correct the BST: 

we could also detect this during inorder traversal. we keep track of previous and next node visited and the two times we see the violations of previous < current or current < next we record these and swap their data
Alternatively, 

Node CorrectBST(Node root) 

{ 

If (root == null) return null; 

Var inorder = new List<Node>(); 

InOrder(root, ref inorder); 

Var swapped = FindSwappedAsTupleFromSequence(inorder); 

// swap the data of the two nodes.

Var temp = Swapped.first.data; 

Swapped.first.data = swapped.second.data; 

Swapped.second.data = temp; 

return root;

}