[Leetcode Solution] Recover Binary Search Tree

GOOD PROBLEM

Analysis

• A inorder traversal of binary search tree results into a ascending order sequence
• Thus a solution using O(n)space is straightforward. By performing inorder traversal and getting the ascending order sequence, it would be quite easy to find out the swapped elements
• A solution using constant space is quite tricky because whether using recursion, the normal inorder traversal needs at least O(logn) space to store the searching status
• The trick is constant inorder traversal found here call Morris In-order Traversal using Threading
• After having constant space traversal method, we check each element while traversal if it is in a correct ascending order
• Another trick is how to deal with the situation that the swapped two elements are adjacent ones

Note

• In-order traversal binary tree in constant space

Code