Given a binary search tree, in which any two nodes are swapped. So we need to find those two nodes and swap them back(we need to swap the nodes, not the data)
I tried to do this by making an additional array which has the inorder traversal of the tree and also saves the pointer to each node. Then we just traverse the array and find the two nodes that are not in the sorted order, now these two nodes are searched in the tree and then swapped
So my question is how to solve this problem in O(1) space ?