Recover Binary Search Tree | Leetcode

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.
 
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

---

Solution: Do in-order traversal and find two nodes that are out-of-order. After the traversal is done, swap the two nodes. I would not think this algorithm is "straight forward". This uses O(log n) space in the stack which is not the right answer.

The right answer is to use Morris Traversal, which uses O(1) space, but I am not sure how anyone can come up with the algorithm in a short time. (http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/)

Algorithm 1: Recursion

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode outOfOrderNode1;
    private TreeNode outOfOrderNode2;
    private TreeNode prevNode;

    public void recoverTree(TreeNode root) {
        findNodesInOrder(root);
        
        // Cheap swap possible in Leetcode.
        // In real life, probably need both parent nodes to do swap.
        int tmp = outOfOrderNode1.val;
        outOfOrderNode1.val = outOfOrderNode2.val;
        outOfOrderNode2.val = tmp;
    }
    
    private void findNodesInOrder(TreeNode node) {
        if (node == null) return;
        findNodesInOrder(node.left);
        
        if (prevNode != null && prevNode.val >= node.val) {
            // Both the previous node and the current node are out-of-order.
            if (outOfOrderNode1 == null) {
                outOfOrderNode1 = prevNode;
            }
            outOfOrderNode2 = node;
        }
        prevNode = node;
        
        findNodesInOrder(node.right);
    }
}

Algorithm 2: Morris Traversal

public class Solution {
    private TreeNode curNode;
    private TreeNode prevNode;
    private TreeNode outOfOrderNode1;
    private TreeNode outOfOrderNode2;

    public void recoverTree(TreeNode root) {
        curNode = root;
        
        while (curNode != null) {
            if (curNode.left == null) {
                checkUpdateOutOfOrderNodes();
                curNode = curNode.right;
                continue;
            }
            
            TreeNode node = curNode.left;
            while (node.right != null && node.right != curNode) {
                node = node.right;
            }
            if (node.right == null) {
                node.right = curNode;
                curNode = curNode.left;
            } else {
                node.right = null;
                checkUpdateOutOfOrderNodes();
                curNode = curNode.right;
            }
        }
        
        int tmp = outOfOrderNode1.val;
        outOfOrderNode1.val = outOfOrderNode2.val;
        outOfOrderNode2.val = tmp;
    }
    
    private void checkUpdateOutOfOrderNodes() {
        if (prevNode != null && prevNode.val >= curNode.val) {
            if (outOfOrderNode1 == null) {
                outOfOrderNode1 = prevNode;
            }
            outOfOrderNode2 = curNode;
        }
        prevNode = curNode;
    }
}