Morris In-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 In-order Traversal.

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
Example:

Input: [1,null,2,3]

Output: [1,3,2]

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

Approach

To solve the problem with Morris In-order Tree Traversal, we have to follow the rules below.

1. if current has no left child,

   • Add current's value to output.
   • current = current.right.

2. if current has left child,

   • make the current the right child of the rightmost node in current's left subtree.
   • current = current.left

note: Don't forget the original current left to be null to avoid infinite loops in rule.2

Here is the example of the traversal.

Solution: Morris In-order Tree Traversal

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        output = []
        current = root

        while current is not None:
            if current.left is None:
                output.append(current.val)
                current = current.right
            else:
                predecessor = current.left
                while predecessor.right:
                    predecessor = predecessor.right 
                predecessor.right = current
                tmp = current
                current = current.left
                tmp.left = None
        return output 

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