Morris

Created in August 20, 2023

2023   ·   Data Structure

Morris traversal of binary Tree

Conception

  1. Nodes without left subtrees will only arrive once, and nodes with left subtrees will arrive twice.
  2. The use of the tree’s leaf nodes around the child is empty (a large number of free pointers of the tree), so as to achieve a rapid reduction in space overhead.

Explain

The node uses the right pointer direction of the rightmost node on the left tree to mark whether it is the first or second time.

  1. If this is the first time you mark yourself, move to the left and use the same strategy to execute the subtree (left tree).
  2. If it is the second time to mark yourself, after the recovery is complete, go to the right subtree to repeat the behavior (1,2).
  1. The node has no left tree and the node only arrives once.
    • If the rightmost node of the left subtree of a node points to empty, the node must be coming for the first time.
  2. The node has a left tree and the node arrives twice.
    • If the rightmost node of the left subtree of the current node points to itself, the node must be coming for the second time.

Details

Suppose the current node cur, and the cur comes to the header node at the beginning.

  1. If cur does not have a left child, cur moves to the right, cur = cur.right.
  2. If cur has a left child, find the rightmost node morrisRight of the left subtree.
    1. If the right pointer of morrisRight points to null, let it point to cur, and then cur moves to the left, cur = cur.left.
    2. If the right pointer of morrisRight points to cur, let it point to null, and then cur moves to the right, cur = cur.right.
  3. Cur is null and traversing stops.

Logic

Recursive order: ①②②②①③③③① [System stack]

Pre-order (the result of the first occurrence): ①②③
Middle order (the result of the second occurrence): ②①③
Post-order (the result of the third occurrence): ②③①

Morris traversal highly simulates recursive behavior

  1. There is no left subtree node and can only be reached once.
  2. There are left subtree nodes, which can reach 2 times.
  3. The node cannot be reached 3 times.

    Morris uses a node to point the right pointer to the left tree to solve this problem.

a, b, c, d, e, f, d, a, g, h, i, h, k, g

Code Content

Suppose the current node cur, and the cur comes to the header node at the beginning.

  1. If cur does not have a left child, cur moves to the right, cur = cur.right.
  2. If cur has a left child, find the rightmost node morrisRight of the left subtree.
    1. If the right pointer of morrisRight points to null, let it point to cur, and then cur moves to the left, cur = cur.left.
    1. If the right pointer of morrisRight points to cur, let it point to null, and then cur moves to the right, cur = cur.right.
  3. Cur is null and traversing stops。

General Code

/**
 * @author zhengstars
 * @date 2023/08/20
 */
public class Morris {

    public static class Node {
        int val;
        Node left;
        Node right;
        Node() {}
        Node(int val) { this.val = val; }
        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
    public static void morris(Node head){
        if(head == null){
            return;
        }

        Node cur = head;
        Node morrisRight = null;

        while (cur != null){
            // morrisRight is cur's left child
            morrisRight = cur.left;
            if(morrisRight != null){
                while (morrisRight.right != null && morrisRight.right != cur){
                    morrisRight = morrisRight.right;
                }

                //After while execution, morrisRight comes to the position of the rightmost child in the left subtree of cur.

                if(morrisRight.right == null){
                    // Come to cur for the first time
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    // Come to cur for the second time, morrisRight.right == cur
                    morrisRight.right = null;
                }
            }
            cur = cur.right;
        }
    }
}

Example


Morris traversal: ①②④②⑤①③⑥③⑦

  • Pre-order (the result of the first occurrence): ①②④⑤③⑥⑦
  • Middle order (the result of the second occurrence): ④②⑤①⑥③⑦

Pre-order traversal

第一次出现的打印

  1. There is no left node printing, there is a left node description to print 2 times
  2. Come to cur to print for the first time
/**
 * @author zhengstars
 * @date 2023/08/20
 */
public class Morris {

    public static class Node {
        int val;
        Node left;
        Node right;
        Node() {}
        Node(int val) { this.val = val; }
        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
    public static void morrisPre(Node head){
        if(head == null){
            return;
        }

        Node cur = head;
        Node morrisRight = null;

        while (cur != null){
            // morrisRight is cur's left child
            morrisRight = cur.left;
            if(morrisRight != null){
                while (morrisRight.right != null && morrisRight.right != cur){
                    morrisRight = morrisRight.right;
                }

                //After while execution, morrisRight comes to the position of the rightmost child in the left subtree of cur.

                if(morrisRight.right == null){ // Come to cur for the first time
                    // --- first time
                    System.out.println(cur.value);
                    
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    // Come to cur for the second time, morrisRight.right == cur
                    morrisRight.right = null;
                }
            }else{
               // --- Arrive at yourself for the first time
               System.out.println(cur.value); 
            }
            cur = cur.right;
        }
    }
}

In-order traversal

  1. The direct output of the node that can only reach itself once
  2. Nodes that can reach themselves twice only print the second time.
/**
 * @author zhengstars
 * @date 2023/08/20
 */
public class Morris {

    public static class Node {
        int val;
        Node left;
        Node right;
        Node() {}
        Node(int val) { this.val = val; }
        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
    public static void morrisIn(Node head){
        if(head == null){
            return;
        }

        Node cur = head;
        Node morrisRight = null;

        while (cur != null){
            // morrisRight is cur's left child
            morrisRight = cur.left;
            if(morrisRight != null){
                while (morrisRight.right != null && morrisRight.right != cur){
                    morrisRight = morrisRight.right;
                }

                //After while execution, morrisRight comes to the position of the rightmost child in the left subtree of cur.

                if(morrisRight.right == null){ // Come to cur for the first time
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue; //--- The first time you enter continue directly, while starts execution again.
                }else{
                    // Come to cur for the second time, morrisRight.right == cur
                    morrisRight.right = null;
                    //--- The second time come in and print directly.
                }
            }
            
           System.out.println(cur.value);

           cur = cur.right;
        }
    }
}

Post-order traversal

Post-order traversal is the third visit before printing.

  1. Morris traversal there is no third visit.
  2. The Post-order can only care about the node that goes back to itself twice. 
     1. Skip the node that you can reach once.
    1. For the node that you can reach twice 
          1. When the second traversal arrives, `the right boundary of the current left subtree is printed in reverse order`.
      1. After traversing, you finally need to print the right boundary of the whole tree in reverse order.
/**
 * @author zhengstars
 * @date 2023/08/20
 */
public class Morris {

    public static class Node {
        int val;
        Node left;
        Node right;
        Node() {}
        Node(int val) { this.val = val; }
        Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
    public static void morrisIn(Node head){
        if(head == null){
            return;
        }

        Node cur = head;
        Node morrisRight = null;

        while (cur != null){
            // morrisRight is cur's left child
            morrisRight = cur.left;
            if(morrisRight != null){
                while (morrisRight.right != null && morrisRight.right != cur){
                    morrisRight = morrisRight.right;
                }

                //After while execution, morrisRight comes to the position of the rightmost child in the left subtree of cur.

                if(morrisRight.right == null){ // Come to cur for the first time
                    morrisRight.right = cur;
                    cur = cur.left;
                    continue; 
                }else{
                    // Come to cur for the second time, morrisRight.right == cur
                    morrisRight.right = null;
                   
                    // --- Print the right boundary of the left subtree of cur in reverse order
                    reversePrintEdge(cur.left);
                }
            }

           cur = cur.right;
        }

       // --- Finally, print the right boundary of the whole tree in reverse order.
       reversePrintEdge(cur.left);
    }

   /**
    * The tree headed by head prints its right boundary in reverse order
    * @param head
    */
   public static void reversePrintEdge(Node head){
        // Get the tail pointer, the rightmost node
        Node tail = reverse(head);
        Node cur = tail;
        while(cur != null){
           System.out.println(cur.value);
           cur = cur.right;
        }
        
        // Reverse again at this time
        reverse(tail);
    }

   /**
    * Reverse change of pointer direction similar to single linked list
    * @param from
    * @return
    */
    public static node reverse(Node from){
        Node pre = null;
        Node next = null;
        
        while(from != null){ // At this time, from is not equal to null because the last one becomes null after being converted to next.
            next = from.right;
            from.right = pre;
            
            pre = from;
            from = next;
        }
        return pre;
    }
    
}

Example


Post-order: ⑧⑨④⑤②⑥⑩⑪⑦③①



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 2379. Minimum Recolors to Get K Consecutive Black Blocks
  • 2471. Minimum Number of Operations to Sort a Binary Tree by Level
  • 1387. Sort Integers by The Power Value
  • 2090. K Radius Subarray Averages
  • 2545. Sort the Students by Their Kth Score