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


  • 44
    H

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

  • 1
    O

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

  • 0
    H
    This post is deleted!

  • 0

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

Log in to reply
 

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