Fix a binary tree that is only one swap away from becoming a BST

Given a binary tree that is only one swap away from becoming a BST, convert the binary tree into BST in single traversal of it.

 

For example, consider binary tree shown on the left side below. It should be converted to BST shown on the right by swapping nodes 2 and 4.


           5                     5        
         /   \                 /   \      
        /     \               /     \     
       3       8     —->     3       8    
      / \     / \           / \     / \   
     /   \   /   \         /   \   /   \  
    4     2 6     10      2     4 6    10 

 

 
We know that an in-order traversal of a binary search tree returns the nodes in sorted order. The idea is to perform perform in-order traversal of the binary tree and keep track of the last visited node while traversing the tree and check whether its key is smaller compared to the current key or not. We mark the nodes where this property is violated and later swap them.

 
C++ implementation –
 

Download   Run Code

Output:

8 10 12 15 16 20 25

 
The time complexity of above solution is O(n).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of