Two nodes of a BST are swapped , correct the BST | Set | C ++ implementation of the above approach ; A binary tree node has data , pointer to left child and a pointer to right child ; Utility function for insertion sort ; Utility function to create a vector with inorder traversal of a binary tree ; Base cases ; Recursive call for left subtree ; Insert node into vector ; Recursive call for right subtree ; Function to exchange data for incorrect nodes ; Base cases ; Recursive call to find the node in left subtree ; Check if current node is incorrect and exchange ; Recursive call to find the node in right subtree ; Primary function to fix the two nodes ; Vector to store the inorder traversal of tree ; Function call to insert nodes into vector ; create a copy of the vector ; Sort the original vector thereby making it a valid BST 's inorder ; Traverse through both vectors and compare misplaced values in original BST ; Find the mismatched values and interchange them ; Find and exchange the data of the two nodes ; As it given only two values are wrong we don 't need to check further ; Return the root of corrected BST ; A utility function to print Inorder traversal ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int data ; struct node * left , * right ; node ( int x ) { data = x ; left = right = NULL ; } } ; void insertionSort ( vector < int > & v , int n ) { int i , key , j ; for ( i = 1 ; i < n ; i ++ ) { key = v [ i ] ; j = i - 1 ; while ( j >= 0 && v [ j ] > key ) { v [ j + 1 ] = v [ j ] ; j = j - 1 ; } v [ j + 1 ] = key ; } } void inorder ( node * root , vector < int > & v ) { if ( ! root ) return ; inorder ( root -> left , v ) ; v . push_back ( root -> data ) ; inorder ( root -> right , v ) ; } void find ( node * root , int res , int res2 ) { if ( ! root ) { return ; } find ( root -> left , res , res2 ) ; if ( root -> data == res ) { root -> data = res2 ; } else if ( root -> data == res2 ) { root -> data = res ; } find ( root -> right , res , res2 ) ; } struct node * correctBST ( struct node * root ) { vector < int > v ; inorder ( root , v ) ; vector < int > v1 = v ; insertionSort ( v , v . size ( ) ) ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { if ( v [ i ] != v1 [ i ] ) { find ( root , v1 [ i ] , v [ i ] ) ; break ; } } return root ; } void printInorder ( struct node * node ) { if ( node == NULL ) return ; printInorder ( node -> left ) ; printf ( " % d ▁ " , node -> data ) ; printInorder ( node -> right ) ; } int main ( ) { struct node * root = new node ( 6 ) ; root -> left = new node ( 10 ) ; root -> right = new node ( 2 ) ; root -> left -> left = new node ( 1 ) ; root -> left -> right = new node ( 3 ) ; root -> right -> right = new node ( 12 ) ; root -> right -> left = new node ( 7 ) ; printf ( " Inorder ▁ Traversal ▁ of ▁ the " ) ; printf ( " original ▁ tree ▁ STRNEWLINE " ) ; printInorder ( root ) ; correctBST ( root ) ; printf ( " Inorder Traversal of the " printf ( " fixed ▁ tree ▁ STRNEWLINE " ) ; printInorder ( root ) ; return 0 ; }