# Java O(1) space O(n) time solution: 5 ms Morris Traversal with explanation

• The space complexity O(1) requires no recursion or stack used, thus it is recommended to use Morris Threading Traversal method to perform an inorder traversal of the BST. Refer to Inorder traversal without stack on Geeksforgeeks.

The inorder traversal of a correct BST should be an ascending array, thus we would like to find the two errors swapped `a[i] (err1)` and `a[j] (err2)`:

`a[1],a[2],a[3],...,a[i],...,a[j],...,a[n]` (index here starts from 1 to illustrate mathematical logic)

For `a[k], k` belongs to `[1,n]`, it is obvious that the first error `err1` is the former element of the first descending pair `a[k] > a[k+1]`: `err1 = a[k] if err1 == null and a[k]>a[k+1]`, similarly, the second error `err2` is the later element of the last descending pair `a[k] > a[k+1]`: `err2 = a[k+1] if a[k]>a[k+1]`

``````public class Solution {
public void recoverTree(TreeNode root) {
TreeNode err1 = null;
TreeNode err2 = null;
TreeNode prev = new TreeNode(Integer.MIN_VALUE); // to store the former element
TreeNode curr = root;
//Morris inorder traversal
while(curr!=null){
TreeNode node = curr.left;
//Check if left subtree is null
if(node==null){
//check curr node to find if it is swapped
if(curr.val<prev.val){
err1 = err1==null?prev:err1;
err2 = curr;
}
prev = curr;
curr = curr.right;
}else{
// find the inorder predecessor
while(node.right!=null&&node.right!=curr){
node = node.right;
}
if(node.right==curr){
//check curr node to find if it is swapped
if(curr.val<prev.val){
err1 = err1==null?prev:err1;
err2 = curr;
}
prev = curr;
node.right = null;
curr = curr.right;
}else{
node.right = curr;
curr = curr.left;
}
}
}
/* Here we swap by value, though swapping the objects is more precise,
it needs the parents nodes and more complex conditional statements:
if the two errors are parent-child or not.
Swapping by value here passes the test
*/
swap(err1,err2);
}

private void swap(TreeNode n1,TreeNode n2){
int temp = n1.val;
n1.val = n2.val;
n2.val = temp;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.