Morris Binary Tree Traversal [space - O(1)]

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values. (link)

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Solution

Moris Algorithm (Threaded Binary Tree)

Time - O(n)

Space - O(1)

Traversal Idea: When traversing the left subtree, we connect the rightmost leaf to the root node. This connection helps us easily return to the root without backtracking while iterating through the left subtree. Meanwhile, we move to the left subtree, complete our tasks, and then return to the root using the connection. We then remove this link by going back to the rightmost leaf and removing the connection before moving to the right subtree.

Note for inorder sequence:

• We add a node to the inorder sequence if it doesn't have a left child. After adding it, we move to the right node.

• Also once the connection is removed and we are back at the root, we add the root to the inorder sequence and then move to the right node.

Inorder

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        TreeNode curr = root;

        List<Integer> ans = new ArrayList<>();
        while(curr!=null){
            if(curr.left==null){
                ans.add(curr.val);
                curr = curr.right;
            }
            else{
                TreeNode rightMost = curr.left;

                while(rightMost.right!=null && rightMost.right!=curr){
                    rightMost = rightMost.right;
                }

                if(rightMost.right==null){
                    rightMost.right = curr;
                    curr = curr.left;
                }
                else{
                    rightMost.right = null;
                    ans.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return ans;
    }
}

Preorder

link

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        TreeNode curr = root;

        while(curr!=null){
            if(curr.left==null){
                ans.add(curr.val);
                curr = curr.right;
            }
            else{
                TreeNode rightMost = curr.left;
                while(rightMost.right!=null && rightMost.right!=curr){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    rightMost.right = curr;
                    ans.add(curr.val);
                    curr = curr.left;
                }
                else{
                    rightMost.right = null;
                    curr = curr.right;
                }
            }
        }
        return ans;
    }
}