Share my solutions and detailed explanation with recursive/iterative in-order-traversal and Morris-traversal

• In-order traversal is really useful in BST. Following in-order traversal, we should have following order: prev.val < curr.val. If not, then we found at least one incorrectly placed node

So the basic idea is to visit the tree with in-order traversal and search for two swapped nodes. Then swap them back.

Now the problem is if we found an incorrect pair where prev.val > curr.val, how do we know which node is the incorrect one? The answer is it depends on whether we have found incorrect node before. So What is that?

Since we get two elements that are swapped by mistake, there must be a smaller TreeNode get a larger value and a larger TreeNode get a smaller value.
Their value are swapped, but the incorrect smaller node is still in smaller tree and incorrect larger node is still in larger tree. So we will visit the incorrect smaller node first, and this node will be detected when we compare its value with next.val, i.e. when it is treated as prev node. The incorrect larger node will be detected when we compare its value with prev.val. We don't know if it is close or not close to incorrect smaller node, so we should continue search BST and update it if we found another incorrect node.

Therefore if it is the first time we found an incorrect pair, the prev node must be the first incorrect node.
If it is not the first time we found an incorrect pair, the curr node must be the second incorrect node, though
we may have corner case that two incorrect nodes are in same pair.

Recursive in-order traversal based on above idea:

``````public void recoverTree(TreeNode root) {
//use inorder traversal to detect incorrect node

inOrder(root);

int temp = first.val;
first.val = second.val;
second.val = temp;
}

TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;

public void inOrder(TreeNode root){
if(root == null) return;
//search left tree
inOrder(root.left);

//in inorder traversal of BST, prev should always have smaller value than current value
if(prev != null && prev.val >= root.val){
//incorrect smaller node is always found as prev node
if(first == null) first = prev;
//incorrect larger node is always found as curr(root) node
second = root;
}

//update prev node
prev = root;

//search right tree
inOrder(root.right);
}
``````

iterative in-order traversal based on above idea:

``````public void recoverTree(TreeNode root) {
TreeNode first = null;
TreeNode second = null;

TreeNode curr = root;
TreeNode prev = null;

Stack<TreeNode> stack = new Stack<TreeNode>();

while(!stack.isEmpty() ||  curr != null){
if(curr != null){
//visit curr's left subtree
stack.push(curr);
curr = curr.left;
}else{
//done left subtree of curr Node
curr = stack.pop();

//compare curr.val with prev.val if we have one
if(prev != null && curr.val <= prev.val){
//incorrect smaller node is always found as prev node
if(first == null) first = prev;
//incorrect larger node is always found as curr node
second = curr;
}

//visit curr's right subtree
prev = curr;
curr = curr.right;
}
}

//recover swapped nodes
int temp = first.val;
first.val = second.val;
second.val = temp;
}
``````

Both recursive and iterative will occupy O(n) space in worst case, in which the tree is like a LinkedList

To reduce the space to constant space, we have to use Morris-traversal.

Morris-traversal is similar to recursive/iterative traversal, but we need to modify the tree structure during the
traversal. before we visiting the left tree of a root, we will build a back-edge between rightmost node in left tree and the root. So we can go back to the root node after we are done with the left tree. Then we locate the rightmost node in left subtree again, cut the back-edge, recover the tree structure and start visit right subtree. The detection of two incorrect TreeNodes is similar to iterative/recursive in-order traversal.
We don't use extra data structure here, so the space complexity is reduced to O(1) and the time complexity will be O(n)

Morris-traversal based on above description:

``````public void recoverTree(TreeNode root) {
//Morris-traversal

TreeNode first = null;
TreeNode second = null;

TreeNode pred = null; //rightmost node in left tree
TreeNode prev = null;

TreeNode curr = root;

while(curr != null){
//for each node, we compare it with prev node as we did in in-order-traversal
if(prev != null && curr.val <= prev.val){
if(first == null) first = prev;
second = curr;
}

if(curr.left != null){
//got left tree, then let's locate its rightmost node in left tree
pred = curr.left;
//we may have visited the left tree before, and connect the rightmost node with curr node (root node)
while(pred.right != null && pred.right != curr){
pred = pred.right;
}

if(pred.right == curr){
//if this left tree has been visited before, then we are done with it
//cut the connection with currNode and start visit curr's right tree
pred.right = null;
prev = curr;
curr = curr.right;
}else{
//if this left tree has not been visited before, then we create a back edge from rightmost node
// to curr node, so we can return to the start point after done the left tree
pred.right = curr;
curr = curr.left;
}

}else{
//no left tree, then just visit its right tree
prev = curr;
curr = curr.right;
}
}

int temp = first.val;
first.val = second.val;
second.val = temp;
}``````

• In my implementation I kept morris traversal template intact and visit each node in a wrapped function. It will be more structured and clearer.

``````public class Solution {
public void recoverTree(TreeNode root) {
TreeNode[] candidates = null;
TreeNode prev = null;

TreeNode p = root; ///Morris Begins///
while (p != null) {
if (p.left == null) {
candidates = checkSeq(prev, p, candidates); //visit p
prev = p; //visit p
p = p.right;
}
else { // p.left != null
TreeNode r = p.left;
while (r.right != null && r.right != p) r = r.right;
if (r.right == null) { // haven't traversed p's left subtree
r.right = p;
p = p.left;
} else { // have traversed all p's left subtree, time to go back to parent
candidates = checkSeq(prev, p, candidates); //visit p
prev = p; //visit p
r.right = null;
p = p.right;
}

}
} ///Morris Ends///

int t = candidates[0].val;
candidates[0].val = candidates[1].val;
candidates[1].val = t;
}

private TreeNode[] checkSeq(TreeNode prev, TreeNode p, TreeNode[] candidates) {
if (prev == null) return candidates;
if (prev.val > p.val) {
if (candidates == null) //first occur
candidates = new TreeNode[]{prev, p};
else
candidates[1] = p; //second occur, update new candidate No.2
}
return candidates;
}
}``````

• This post is deleted!

• Share:

``````TreeNode  previous = null;
TreeNode firstWrongTree = null;
TreeNode secondWrongTree = null;

public void recoverTree(TreeNode root) {
traverse(root);
int tmp = firstWrongTree.val;
firstWrongTree.val = secondWrongTree.val;
secondWrongTree.val = tmp;
}

private void traverse(TreeNode node) {
if (node == null) return;
traverse(node.left);
if(previous != null){
if(previous.val >= node.val){
if(firstWrongTree == null)
firstWrongTree = previous;
secondWrongTree = node;
}
}
previous = node;
traverse(node.right);
}``````

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