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


  • 0
    Z

    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;
        }
    }
    

Log in to reply
 

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