DEV Community

Shoryu
Shoryu

Posted on • Updated on

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.

Alt Text

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.

Top comments (0)