Recover binary search tree

#1

i am unable to this problem…pls tell the code.

#2

@yutikakhanna hey,Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST.
Input Tree:
10
/
5 8
/
2 20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.
Following is the output tree
10
/
5 20
/
2 8

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.

#3

tried implementing this…but getting error. pls tell the code

#4

@yutikakhanna hey,here is the code for reference ,feel free to ask any doubt:

#5

pls provide the entire code…this is the function part only

#6

@yutikakhanna hi this is complete code:https://ide.codingblocks.com/s/219604

#7

this is showing a few errors

#8

@yutikakhanna hey,apko woh input khud lena pdega in form of vector aur isko main me likho ,hojayega submit.

#9

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.