title: Find swapped nodes in a BST
body: <p>I am trying to write a program that can detect and print two nodes in BST that have been swapped.</p>
  
  <p>In a three level tree, I reached near to the solution using this approach.</p>
  
  <pre><code>If (!AllSubTreeAreValid())
  {
  //Nodes swapped on same side of main root node
  }
  else
  {
    int max = getMax(root-&gt;left);
    int min = getMin(root-&gt;right);
    if(max &gt; root-&gt;data || min &lt; root-&gt;data )
    {
       //Nodes swapped on different sides of main root node
       //Print max and min values
  
    }
  else 
  {
   //No node swappped
  }
  }
  
  //Helper functions
  int GetMaxEle(TreeNode* tree)
  {
      while(tree-&gt;right!=NULL)
      {
          tree=tree-&gt;right;
      }
      return tree-&gt;info;
  }
  
  int GetMinEle(TreeNode* tree)
  {
      while(tree-&gt;left!=NULL)
      {
          tree=tree-&gt;left;
      }
      return tree-&gt;info;
  }
  </code></pre>
  
  <p>but the above approach failed when I tried to test with four level tree.</p>
  
  <pre><code>             20
  
        15            30
  
     10    17       25     33
  
  9  16  12  18  22  26  31  34
  </code></pre>
  
  <p>Being in root node 15's right subtree, 12 is still greater (violation).</p>
  
  <p>Being in root node 15's left subtree, 16 is still greater (violation).</p>
  
  <p>So, 16, 12 are the swapped elements in the above BST. How do I find them through the program? </p>