Christopher SuAbout Blog Projects Contact More

Problem

Two nodes in a binary search tree have been swapped. Correct the tree to restore its original ordering.
Generalize this to 2, 3, n swapped pairs of nodes.

Solution

Solution is of \( O(N) \) time.
You can either store an in-order traversal in an array and then iterate through the array looking for the elements that are out of place, or you can maintain pointers as you traverse the tree to keep track of the out-of-place nodes. Swap them once two are found.