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 –

Download   Run Code


8 10 12 15 16 20 25

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

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of