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.
 
Fix a Binary Tree
 
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 –
 
Output:

8 10 12 15 16 20 25
 
The time complexity of above solution is O(n).

Comments

Popular posts from this blog

How to change this to <%Html.ActionLink%> in my asp.net mvc application ?