Correct BST with two nodes swapped

Hard

In-order finds exactly the two anomalies

Problem

Two nodes of a BST were swapped by mistake. Recover the BST by fixing them (in place).

In simple words

The in-order walk of a BST is sorted; find the two out-of-place values and swap them back.

The idea

An in-order traversal of a correct BST is strictly increasing, so swapping two nodes creates either one or two descents. The first descent's earlier node and the last descent's later node are the swapped pair — swap their values back.

The trick

Adjacent nodes swapped produce one violation; distant nodes produce two.
Track first, middle and last violation candidates during the traversal.
Morris traversal does it in O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(n)spaceO(h)

1inorder walk tracking prev2find first place prev>cur (first, middle) and last (last)3swap values of the two offenders

Input

array: [3, 1, 4, 2]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [3,1,4,null,null,2]
Output:: [1, 2, 3, 4]
Explanation:: Two nodes are swapped; fixing gives sorted in-order.

Example 2

Input:: tree = [2,3,1]
Output:: [1, 2, 3]
Explanation:: Correct in-order becomes 1,2,3.

Example 3

Input:: tree = [1,2]
Output:: [1, 2]
Explanation:: Restore proper BST order.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.