Programming Interview Question: Recover Binary Search Tree

If two nodes of a binary search tree (BST) are swapped by mistake. Restore the BST structure without changing positions of nodes which are correctly placed.

[falakk]

I really wish that rest of tree problems had videos like this one . Please consider the request to add videos, Ideserve is a reference for all kind of DS Problems :)) . Thanks

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[lokeshkoliparthi]

Very Well Explained!!! Became fan of this channel after seeing very few videos.
Thank You in advance for your future videos.

[arjunpassi]

How do we know the elements are swapped? The second example that you show @ 0:39 there is no way to know that 3 and 5 were swapped as the BST properties are not violated.

[latasingh]

simple and easy explanation of the algo that first seems to be typical. keep the hard work !!

[rahulshah]

Brilliant. You should carry on with this work.

[ishanikasingh]

kudos to your explaination, brilliant!

[jagdishwarbiradar]

why do we traverse a tree in inorder and store value of each node in array, then sort and make a tree by the sorted array can we do that?

[harishkandikatla]

What is space complexity for this solution, is it O(n) or O(1)?
I'm confused as recursion is never space O(1)

[namangupta]

I used the same procedure, but my code is giving the wrong answer, is there any correction in this method?

[ShreyaSingh-vrqi]

You are swapping data of nodes, not nodes ?