Recover Binary Search Tree

#1

kindly help in understanding my error using the code

#2

Hello @Legendankit,

Please, share the question with me.

#3

Two elements of a binary search tree (BST) are swapped by mistake. Tell us the 2 values swapping which the tree will be restored.

Input Format
First line contains n denoting the input size.
Next line contains n space separated integers denoting the preorder input of the tree.

NOTE : -1 indicates that the node does not exist.

Constraints
1 <= n <= 10^5
Your recovery algorithm should work in O(n) time.

#4

Hello @Legendankit,

I am really sorry for replying this laste.

Since inorder traversal of BST is always a sorted array, the problem can be reduced to a problem where two elements of a sorted array are swapped. There are two cases that we need to handle:

  1. The swapped nodes are not adjacent in the inorder traversal of the BST.

For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 25 7 8 10 15 20 5
If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.

  1. The swapped nodes are adjacent in the inorder traversal of BST.

For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 5 8 7 10 15 20 25
Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.

Let me know if you face any problem.

#5

Sorry to say but couldn’t get it

#6

Hello @Legendankit,

No, need to be sorry.

Let’s understand it with the help of the code segment:

Hope, this would help.

#7

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.