In a BST two nodes are randomly swapped we need to find those two nodes and swap them back

Question

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 ?

Answer 1

In order traversal on a BST gives you a traversal on the elements, ordered.
You can use an in-order traversal, find the two out of place elements (store them in two pointers) and swap them back.

This method is actually creating the array you described on the fly, without actually creating it.

Note that however, space consumption is not O(1), it is O(h) where h is the height of the tree, due to the stack trace. If the tree is balanced, it will be O(logn)