Morris Traversal Morris Pre-order Tree Traversal

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

The pattern of Tree Traversal

Here are three patterns for Tree Traversal.

Each patten has only one order.

• Pre-order Traversal
  • root -> left -> right
• In-order Traversal
  • left -> root -> right
• Post-order Traversal
  • right -> left -> root

Problem

Today's problem is about Pre-order Traversal.

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]

Output: [1,2,3]

We have to put the values of Input in Pre-order, which is root -> left -> right.

Approach

To solve the problem with Morris Traversal, we have to follow the four steps below.

1. go one step left if possible and then go right till the end.
2. add Node to output and establish the link predecessor.right = node.
3. When we visit the same predecessor the second time, it already points to the current node, thus we remove the link created at step2 and move to right node with node = node.right.
4. return step1

• note: If the step1 is impossible, add node to output and move right to next node.

Here are the points you should remember.

• Add output when node has no left node or predecessors.right is null.
• when predecessor has no right node, make the link from predecessor to node.
• after making the link from predecessor to node, move the node to left.
• after delete the link from predecessor to node, move the node to right.

Here is the example of the traversal.

Solution: Morris Pre-order Tree Traversal

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :type: List[int]
        """
        node = root
        output = []
        while node:
            if node.left is None:
                output.append(node.val)
                node = node.right
            else:                
                predecessor = node.left
                while predecessor.right and predecessor.right is not node:
                    predecessor = predecessor.right
                if predecessor.right is None:
                    output.append(node.val)
                    predecessor.right = node
                    node = node.left
                else:
                    predecessor.right = None
                    node = node.right
        return output

Thank you for reading this article!
I always welcome your feedback, question, and idea.