Recover BST by swapping

#1

Please rectify code and also explain correct logic.

#2

@vidit.103 wait will provide the correct logic

#3

Recover Binary Search Tree

Problem Statement :

Given a BST with two nodes swapped , recover the original BST without changing the structure.

As we all know the inorder traversal of a BST gives a sorted array of integers .

Let’s say [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] be the inorder traversal of some correct BST.

If any two nodes were to be swapped , the traversal will look like [ 1 , 6 , 3 , 4 , 5 , 2 , 7 ]

So one approach that comes to mind is just store the inorder traversal of the BST and iterate over it to get the two nodes that have to be swapped .

But this approach will take o(n) space where n is the no of elements in the BST.

Q : Can we do it in constant space ?

A : Yes we can do it in o(1) space

Let’s observe the traversal we got after swapping two nodes -

[ 1 , 6 , 3 , 4 , 5 , 2 , 7 ]

We can see that in this array after swapping the values two nodes will not be in their correct position ( or we can say that for some of the two adjacent values in the array the first one will be greater than second ) . In this case 6>3 and 5>2 as 6 and 2 are swapped.

So basically we can just maintain a prev pointer and if current < prev then we found one of the wrong nodes. Similarly we can find the other one. But there can be two cases in it :

Case 1 ( swapped nodes are not adjacent )

Example : [ 1 , 6 , 3 , 4 , 5 , 2 , 7 ]

So the first pair we get 6 > 3 and one of our wrong node becomes 6

Then second wrong node will be found when 5>2 so second becomes 2

Note carefully in the first pair 6>3 we took the first one as a wrong node ie 6 and in the second pair 5>2 we took the second one as wrong node ie 2

Also we can’t get more than 2 pairs because exactly 2 nodes are swapped.

So just swap 2 and 6 to recover the BST.

Case 2 ( adjacent nodes are swapped )

Example : [ 1 , 3 , 2 , 4 , 5 , 6 , 7 ]

So in this case we only have one pair 3>2 so our wrong nodes become {2,3} and we can simply swap them.

So our space complexity got reduced to O(1) from O(n) as now we are only maintaining a prev pointer to store what’s behind the current node in the array.

Time Complexity : O(n)

Space Complexity: O(1)

Solution Link : https://ide.codingblocks.com/s/315113

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.