Morris In-order Tree Traversal

#python #leetcode #beginners #algorithms

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.

if current has no left child,
- Add current's value to output.
- current = current.right.
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