Найти поменянные узлы в BST

Я пытаюсь написать программу, которая может обнаружить и печатать два узла в BST, которые были поменяются.

На трехуровневом дереве я добрался до решения, используя этот подход.

If (!AllSubTreeAreValid())
{
//Nodes swapped on same side of main root node
}
else
{
  int max = getMax(root->left);
  int min = getMin(root->right);
  if(max > root->data || min < root->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->right!=NULL)
    {
        tree=tree->right;
    }
    return tree->info;
}

int GetMinEle(TreeNode* tree)
{
    while(tree->left!=NULL)
    {
        tree=tree->left;
    }
    return tree->info;
}

Но приведенный выше подход не удался, когда я попытался проверить с четырьмя уровнями дерева.

             20

      15            30

   10    17       25     33

9  16  12  18  22  26  31  34

Быть в правом верхнем узере корневого узла, 12 все еще больше (нарушение).

Быть в левом левом узере корневого узла, 16 все еще больше (нарушение).

Итак, 16, 12 - это поменяемые элементы в приведенном выше BST. Как мне найти их через программу?