Morris traversal

1. Introduction

Whether we traverse the binary tree recursively or nonrecursively, we can only achieve O(N) time complexity, O(logN) extra space complexity, not O(1) extra space complexity.

Because the essence of traversing a binary tree recursively is that the system pushes us, and the essence of traversing a binary tree non-recursively is that we push ourselves, and all nodes along the path of traversing a binary tree have to be pushed onto the stack.

Morris a way of traversing a binary tree with O(N) time and O(1) extra space.

Morris traversals save space by taking advantage of a large number of idle Pointers to leaf nodes in the tree.

On the basis of Morris traversal, preorder traversal, middle order traversal and subsequent traversal can be processed.

Why is Morris traversal important?

Because there are so many ways to do tree traversal, if you find a way to do tree traversal that’s better than any of the other ways, that means it’s better than any of the other ways.

Morris traversals do not work if it is strictly forbidden to modify the structure of a tree while traversing it.

Morris traversal has another scientific name: clue binary tree.

2. Process

Cur starts at the root node:

If cur has left children, find mostRight, the right-most node on the left child tree
- If the right pointer of mostRight points to null, make it point to cur, and then move it left (cur = cur.left).
- If the right pointer of mostRight points to cur, let it point to null, and then move it to the right (cur = cur.right)
If cur has no left children, cur moves right (cur = cur.right)
Cur is empty when traversal stops

3. The analysis

During Morris traversal, if a node has a left child, it must be accessed twice. If a node has no left child, it can be accessed only once.

When Morris iterates through a node with a left child, can you tell how many times the node is accessed?

Yes, according to the right pointer to the rightmost node in the left subtree of the node. If right points to NULL, it is the first access; If right points to the node itself, it is the second access.

4. The real

Here is the standard recursive version of binary tree traversal:

public static void process(Node root) {
    if (root == null) {
        return ;
    }
    // Access this node for the first time
    process(root.left);
    // Access the node a second time
    process(root.right);
    // Access the node for the third time
}
Copy the code

In recursive traversal of binary trees, each node is treated as root, or returned if root is null. Otherwise, go to the left subtree of root, go back to root, go to the right subtree of root, and go back to root.

This is actually according to the system automatic stack and stack to achieve recursive function call and return, so that each node will be visited three times, to build a recursive sequence of binary tree traversal.

Morris is actually a simulation of a recursive function, but it only allows a node root to traverse the left subtree of root and return to root if it has left children, not traverse one side of the right subtree of root and return to root. If a node root has no left child, it can only be accessed once.

This is actually achieved by using the relationship of underlying clues, so that the nodes with left children can be visited twice, and the nodes without left children can be visited once, constructing the Morris sequence.

5. Implement

public static void morrisTraversal(Node root) {
    if (root == null) {
        return ;
    }

    Node cur = root;
    // The traversal stops when the current node is empty
    while(cur ! =null) {
        / / print
        System.out.println(cur.value);

        // If the current node has left children
        if(cur.left ! =null) {
            // Find the right-most node on the left subtree
            Node mostRight = cur.left;
            // The right of mostRight may not have been changed (first access) or may have been changed (second access)
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }// If mostRight right points to null (first access cur)
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            }
            // If mostRight's right points to cur (second visit cur)
            else {
                mostRight.right = null; cur = cur.right; }}// If the current node has no left child
        else{ cur = cur.right; }}}Copy the code

Complexity of 6.

The additional spatial complexity of the Morris traversal is obviously O(1), because we only prepared two variables, cur and mostRight, as we can see from the program.

The time complexity of Morris traversal is O(N).

For time complexity, we need to consider the following question:

In Morris traversal, every node with a left child needs to find the right-most node of the node’s left subtree. Will this operation increase the time complexity of the whole process?

Let’s calculate the total cost of finding the rightmost node in the left subtree of all nodes in a Morris traversal.

First look at which nodes will find the right-most node of the node’s left subtree, and list the search path:

Node 1 traverses nodes 2, 5, and 11 twice.

Two nodes are traversed twice. Four, nine nodes.

Three nodes are traversed twice six and 13 nodes.

Four nodes are traversed twice by eight nodes.

Five nodes are traversed twice by ten nodes.

Six nodes are traversed twice with twelve nodes.

Seven nodes are traversed twice. Fourteen nodes are traversed.

We find that all nodes that need to find the right-most node of the left subtree are not duplicated during the search.

The total cost of traversing these nodes is approximating O(N).

That is to say, the operation of finding the rightmost node of the left subtree for every node with a left child is O(N).

7. Traversal first

Morris traversal is processed into sequential traversal using the following rules:

If a node can be accessed only once, print when accessed.
If a node can be accessed twice, print the first time it is accessed.

Implementation code:

public static void preMorrisTraversal(Node root) {
    if (root == null) {
        return ;
    }

    Node cur = root;
    // The traversal stops when the current node is empty
    while(cur ! =null) {
        // If the current node has left children
        if(cur.left ! =null) {
            // Find the right-most node on the left subtree
            Node mostRight = cur.left;
            // The right of mostRight may not have been changed (first access) or may have been changed (second access)
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }// If mostRight right points to null (first access cur)
            if (mostRight.right == null) {
                // Print when accessing the first time
                System.out.println(cur.value);

                mostRight.right = cur;
                cur = cur.left;
            }
            // If mostRight's right points to cur (second visit cur)
            else {
                mostRight.right = null; cur = cur.right; }}// If the current node has no left child
        else {
            // Print while accessingSystem.out.println(cur.value); cur = cur.right; }}}Copy the code

8. Middle order traversal

Morris traversal is processed into middle-order traversal according to the following rules:

If a node can be accessed only once, print when accessed.
If a node can be accessed twice, print it on the second access.

Implementation code:

public static void inMorrisTraversal(Node root) {
    if (root == null) {
        return ;
    }

    Node cur = root;
    // The traversal stops when the current node is empty
    while(cur ! =null) {

        // If the current node has left children
        if(cur.left ! =null) {
            // Find the right-most node on the left subtree
            Node mostRight = cur.left;
            // The right of mostRight may not have been changed (first access) or may have been changed (second access)
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }// If mostRight right points to null (first access cur)
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            }
            // If mostRight's right points to cur (second visit cur)
            else {
                // Prints when accessed the second time
                System.out.println(cur.value);

                mostRight.right = null; cur = cur.right; }}// If the current node has no left child
        else {
            // Print while accessingSystem.out.println(cur.value); cur = cur.right; }}}Copy the code

9. Post-order traversal

Morris traversal is processed into middle-order traversal according to the following rules:

If a node can be accessed twice, the bottom-up right boundary of the node’s left subtree is printed on the second access.
When all nodes have been traversed, the right edge of the entire tree is printed separately from the bottom up.

Before the code can be implemented, we need to solve the problem of bottom-up printing and keep the extra space complexity of bottom-up printing to O(1).

As shown in the figure above, the right boundary of the binary tree is: A, B, C, D. The right boundary of the bottom-up printing of the binary tree is: D, C, B, A.

How to print the right boundary in sequence against the binary tree with only a limited number of variables?

The right boundary is regarded as a one-way linked list as a whole, and the right of each node is regarded as the next of nodes in a single necklace list and points to the parent node of each node. If there is no parent node, it points to null, and the left pointing of each node remains unchanged. After adjustment, the printing starts from bottom up, and the original pointing of right is restored after printing.

According to the above idea, we need to design two functions, one function to invert the right boundary, one function to print the right boundary.

// Prints the bottom-up right border of the root tree
public static void printRightEdge(Node root) {
    // Invert the right boundary and get the bottom node of the right boundary
    Node tail = reverseRightEdge(root);

    Node cur = tail;
    while(cur ! =null) {
        / / print
        System.out.println(cur.value);

        cur = cur.right;
    }

    // Reverse the right boundary back
    reverseRightEdge(tail);
}

// Invert the right edge of the root tree
public static Node reverseRightEdge(Node root) {
    Node pre = null;
    Node next = null;

    while(root ! =null) {
        next = root.right;
        root.right = pre;
        pre = root;
        root = next;
    }

    return pre;
}
Copy the code

Implementation code:

public static void postMorrisTraversal(Node root) {
    if (root == null) {
        return ;
    }

    Node cur = root;
    // The traversal stops when the current node is empty
    while(cur ! =null) {

        // If the current node has left children
        if(cur.left ! =null) {
            // Find the right-most node on the left subtree
            Node mostRight = cur.left;
            // The right of mostRight may not have been changed (first access) or may have been changed (second access)
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }// If mostRight right points to null (first access cur)
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            }
            // If mostRight's right points to cur (second visit cur)
            else {
                mostRight.right = null;

                Print the right edge of the left subtree in reverse order on the second accessprintRightEdge(cur.left); cur = cur.right; }}// If the current node has no left child
        else{ cur = cur.right; }}// When all nodes are traversed, print the right edge of the entire tree in reverse order
    printRightEdge(root);
}
Copy the code

10. Comparison with binary tree recursive routines

In the previous “Binary tree Basics”, we described the recursion of binary trees as the optimal solution to solve some problems in binary trees. In this article, we describe Morris traversal as an optimal solution to some problems in binary trees.

Which binomial tree problems are best solved by recursion of binomial trees? Which binomial tree problems have Morris traversal as their optimal solution?

If you find that your method must do a third strong integration of information, use only the recursion of the binary tree, and the recursion of the binary tree is the optimal solution.

The strong integration of the third time information means that a node must obtain the information of its left and right subtrees, and then integrate and return the information of its left and right subtrees with its own information when it visits itself for the third time.
If you find that your method does not require a third strong integration of information, you can use the recursive path of binary trees, or you can use Morris traversal, but Morris traversal is the optimal solution.

Judge search binary tree

How to determine if a tree is a binary search tree?

Analysis:

If the sequence traversed in the middle order is ascending, the tree is a search binary tree.

This problem using Morris traversal will save a lot of space than the conventional solution, and is the optimal solution in this problem.

Code:

public static boolean isBST(Node root) {
    if (root == null) {
        return true;
    }

    // Record the value of the node before the current node
    int preValue = Integer.MIN_VALUE;

    Node cur = root;
    // The traversal stops when the current node is empty
    while(cur ! =null) {
        // If the current node has left children
        if(cur.left ! =null) {
            // Find the right-most node on the left subtree
            Node mostRight = cur.left;
            // The right of mostRight may not have been changed (first access) or may have been changed (second access)
            while(mostRight.right ! =null&& mostRight.right ! = cur) { mostRight = mostRight.right; }// If mostRight right points to null (first access cur)
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            }
            // If mostRight's right points to cur (second visit cur)
            else {
                // Compare with the value of the previous node
                if (cur.value <= preValue) {
                    return false;
                }
                preValue = cur.value;

                mostRight.right = null; cur = cur.right; }}// If the current node has no left child
        else {
            // Compare with the value of the previous node
            if (cur.value <= preValue) {
                return false; } preValue = cur.value; cur = cur.right; }}return true;
}
Copy the code

Morris traversal