Fix binary search tree with 2 swapped nodes

By | February 23, 2016

Fix binary search tree with 2 swapped nodes

Problem statement to fix binary search tree (BST) with two swapped nodes.

We are given a binary search tree (BST) where exactly two nodes are swapped. The aim is to output the corrected BST.

Example for a binary search  tree where two nodes are interchanged:

Input:
                7
             /     \
            5        10
          /   \     /   \
         3     12  8     6
NOTE that 12 and 6 are wrongly placed
Output:
                7
             /     \
            5        10
          /   \     /   \
         3     6   8     12

Solution to correct the Binary Search Tree (BST) when 2 nodes are swapped:

According to binary search tree (BST) property, elements of left subtree must be smaller than the root and elements of right subtree must be greater than the root.
When the elements are swapped, this property is disrupted and this can be checked through inorder traversal.If the next element is smaller then the current in inorder traversal, then it has been swapped.

Algorithm to fix binary search tree with 2 swapped nodes:

  1. Create three pointers i.e.first, middle, last.
  2. Increment the pointers till the value of current node is smaller than that of previous node. Mark previous and current as first and middle nodes respectively.
  3. Check for another discrepancy. If it exists, mark this node as last.
  4. If last pointer is not NULL, swap first and last.
  5. Else swap first and middle nodes.

Code in C++ to fix 2 swapped nodes of a binary search tree.

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This funciton is used to Insert
 new values in BST*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*Function to swap 2 integers*/
void swap(int *a, int *b)
{
   int temp = *a;
   *a = *b;
   *b = temp;
}

/*Funtion to fix the BST*/
void fixBST(node *root, node **first, node **middle,
node **last, node **prev)
{
   if(root)
   {
      /*Recursively check in left subtree*/
      fixBST(root->left, first, middle, last, prev);
      
      /*If current is less than prev, declare 
      them as middle and first resp*/
      if(*prev && root->data < (*prev)->data)
      {
         if(!*first)
         {
            *first = *prev;
            *middle = root;
         }
         
         else
            *last = root;
      }
      
      *prev = root;
      
      /*Recursively check in right subtree*/
      fixBST(root->right, first, middle, last, prev);
   }
}

/*Function to initialize fixBST()*/
void correctBST(node *root)
{
   node *first, *middle, *last, *prev;
   first = middle = last = prev = NULL;
   
   /*Set the pointers to find out two nodes*/
    fixBST( root, &first, &middle, &last, &prev );
 
    // Fix the tree
    if( first && last )
        swap( &(first->data), &(last->data) );
    
    /* Adjacent nodes swapped*/
    else if( first && middle ) 
        swap( &(first->data), &(middle->data) );
}

int main() {
   /* Let us create following BST
              7
            /    \
           5      10
         /  \    /  \
        3    12  8   6
    where we swap 6 and 12 in corrected BST*/
    node *root = NULL;
    root = Insert(root, 7);
    root->left        = newNode(5);
    root->right       = newNode(10);
    root->left->left  = newNode(3);
    root->left->right = newNode(12);
    root->right->right = newNode(6);
    root->right->left = newNode(8);
 
    cout << "Inorder traversal of the BST with 
    swapped nodes is: ";
    Inorder(root);
 
    correctBST(root);
 
    cout << "\nInorder traversal of the fixed BST is: ";
    Inorder(root);
   return 0;
}

OUTPUT:

Inorder traversal of the BST with swapped nodes is: 3 5 12 7 8 10 6 
Inorder traversal of the fixed BST is: 3 5 6 7 8 10 12

 Time Complexity: O(n)