L37. Morris Traversal | Preorder | Inorder | C++ | Java

Mastering Morris Traversal—an ingenious algorithm that achieves Binary Tree Inorder and Preorder traversals in $O(N)$ time complexity and $O(1)$ auxiliary space complexity without utilizing recursion stacks or explicit parent pointers by temporarily modifying tree pointers into threaded links.

1. Why Do We Need Morris Traversal? (The Space Problem)

Standard tree traversals—whether recursive or iterative using a stack—rely heavily on auxiliary memory to remember the path back to the parent nodes.

• The Status Quo: Standard traversals take $O(N)$ Time and $O(N)$ Space (in the worst-case scenario of a skewed tree, or $O(\log N)$ for a balanced tree) because the system call stack or explicit stack stores node references.
• The Morris Traversal Objective: Can we traverse a binary tree in $O(N)$ time while consuming $O(1)$ extra space (zero auxiliary stack space)?
• The Catch: To do this without a stack, we need a way to return to the parent node after visiting the left subtree. Morris Traversal achieves this by temporarily modifying the tree itself—creating "threads" (pointers back to ancestors) and later removing them to restore the tree to its original state.

2. Core Mental Model: Threaded Binary Trees & The Safety Rope

Real-Life Analogy: Exploring a Maze with a Safety Rope

Imagine exploring a complex cave network (a binary tree) where you cannot leave breadcrumbs or carry a map (no stack memory). When you reach a dead end or finish exploring a left passage, how do you find your way back to the main junction?

• You tie a temporary rope (a thread) from the deepest point of your current left exploration directly back to the junction node (the predecessor).
• Once you finish exploring that branch and loop back via the rope, you untie the rope so the cave returns to its original condition.

The Mechanism of Threads

• When standing at a curr node that has a left child, we look into its left subtree.
• We find the rightmost node of that left subtree (which is the Inorder Predecessor of curr).
• Instead of letting that rightmost node's right pointer be null, we temporarily point it to curr.
• This creates a thread, acting as a bridge so that when we finish the left subtree, we can glide right back to curr without a stack!

3. Step-by-Step Evolution: The Inorder Traversal Logic

Let's trace how the algorithm decides whether to create a thread or traverse forward:

1. Initialize: Set curr = root.
2. Loop Condition: While curr != null:
   • Case A: No Left Child (curr.left == null)
     • Since there is no left subtree to process, we can immediately process (print/store) curr.
     • Move to the right: curr = curr.right.
   • Case B: Left Child Exists (curr.left != null)
     • Find the inorder predecessor of curr. Start at prev = curr.left, then keep moving prev = prev.right as long as prev.right is not null AND prev.right != curr.
     • Sub-case B1: The thread does not exist yet (prev.right == null)
       • Create the thread: set prev.right = curr.
       • Move deeper into the left subtree: curr = curr.left.
     • Sub-case B2: The thread already exists (prev.right == curr)
       • The left subtree has already been visited! We need to destroy the thread to restore the tree.
       • Remove the thread: set prev.right = null.
       • Process the current node: visit/print curr.
       • Move to the right subtree: curr = curr.right.

4. Complete Walkthrough of Inorder Morris Traversal

Consider a simple binary tree:

        1
       / \
      2   3
     / \
    4   5

Trace Steps:

1. curr = 1. Has left (2). Predecessor of 1 in left subtree is 5.
   • 5.right is currently null. Create thread: 5.right = 1.
   • Move left: curr = 2.
2. curr = 2. Has left (4). Predecessor of 2 is 4.
   • 4.right is null. Create thread: 4.right = 2.
   • Move left: curr = 4.
3. curr = 4. Has no left child.
   • Process 4.
   • Move right (4.right points to 2 via thread): curr = 2.
4. curr = 2. Has left (4). Predecessor 4 now points to 2 (prev.right == curr).
   • Thread already exists! Remove thread: 4.right = null.
   • Process 2.
   • Move right: curr = 5.
5. curr = 5. Has no left child.
   • Process 5.
   • Move right (5.right points to 1 via thread): curr = 1.
6. curr = 1. Has left (2). Predecessor 5 now points to 1 (prev.right == curr).
   • Thread already exists! Remove thread: 5.right = null.
   • Process 1.
   • Move right: curr = 3.
7. curr = 3. Has no left child.
   • Process 3.
   • Move right: curr = null (Termination).

Final Inorder Output: 4 -> 2 -> 5 -> 1 -> 3

5. Adapting Morris Traversal for Preorder Traversal

The transition from Inorder to Preorder is remarkably simple. Recall the definitions:

• Inorder: Left -> Root -> Right (We process Root after coming back from the left subtree).
• Preorder: Root -> Left -> Right (We process Root before going down the left subtree).

Preorder Code Adjustment Rule:

Instead of printing/storing curr when we destroy the thread (which happens after the left subtree), we print/store curr at the moment we create the thread (before descending into the left subtree), provided there is a left child. If there is no left child, we print curr immediately when visiting it.

6. Implementation Code (C++ and Java)

C++ Implementation (Inorder & Preorder)

#include <vector>
#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> getInorder(TreeNode* root) {
        vector<int> inorder;
        TreeNode* curr = root;
        
        while (curr != nullptr) {
            if (curr->left == nullptr) {
                inorder.push_back(curr->val);
                curr = curr->right;
            } else {
                // Find the inorder predecessor (rightmost node in left subtree)
                TreeNode* prev = curr->left;
                while (prev->right != nullptr && prev->right != curr) {
                    prev = prev->right;
                }
                
                if (prev->right == nullptr) {
                    // Create thread
                    prev->right = curr;
                    curr = curr->left;
                } else {
                    // Thread already exists, break it, process, and move right
                    prev->right = nullptr;
                    inorder.push_back(curr->val);
                    curr = curr->right;
                }
            }
        }
        return inorder;
    }

    vector<int> getPreorder(TreeNode* root) {
        vector<int> preorder;
        TreeNode* curr = root;
        
        while (curr != nullptr) {
            if (curr->left == nullptr) {
                preorder.push_back(curr->val);
                curr = curr->right;
            } else {
                TreeNode* prev = curr->left;
                while (prev->right != nullptr && prev->right != curr) {
                    prev = prev->right;
                }
                
                if (prev->right == nullptr) {
                    // Create thread AND process root immediately for Preorder
                    prev->right = curr;
                    preorder.push_back(curr->val);
                    curr = curr->left;
                } else {
                    // Thread already exists, just break it and move right
                    prev->right = nullptr;
                    curr = curr->right;
                }
            }
        }
        return preorder;
    }
};

Java Implementation (Inorder & Preorder)

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> getInorder(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        TreeNode curr = root;
        
        while (curr != null) {
            if (curr.left == null) {
                inorder.add(curr.val);
                curr = curr.right;
            } else {
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                
                if (prev.right == null) {
                    prev.right = curr; // Create thread
                    curr = curr.left;
                } else {
                    prev.right = null; // Break thread
                    inorder.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return inorder;
    }

    public List<Integer> getPreorder(TreeNode root) {
        List<Integer> preorder = new ArrayList<>();
        TreeNode curr = root;
        
        while (curr != null) {
            if (curr.left == null) {
                preorder.add(curr.val);
                curr = curr.right;
            } else {
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                
                if (prev.right == null) {
                    prev.right = curr; // Create thread
                    preorder.add(curr.val); // Process root immediately
                    curr = curr.left;
                } else {
                    prev.right = null; // Break thread
                    curr = curr.right;
                }
            }
        }
        return preorder;
    }
}

7. Complexity Analysis & The $O(N)$ Time Proof

A common interview question regarding Morris Traversal is: How can it be $O(N)$ time if we are traversing down left subtrees and then traversing back up to find predecessors?

8. Summary and Key Takeaways

• Space Optimization Marvel: Morris Traversal solves binary tree traversal in $O(1)$ auxiliary space, eliminating the need for recursion or explicit stacks.
• Threaded Binary Tree Concept: It dynamically creates temporary pointer links (predecessor.right = curr) to remember parent pathways without extra memory.
• Restoration Guarantee: Every thread created during the traversal is systematically destroyed before the algorithm finishes, leaving the original tree structure completely intact.
• Inorder vs. Preorder Placement:
  • For Inorder, process the node when removing the thread (or when no left child exists).
  • For Preorder, process the node when creating the thread (or when no left child exists).
• Amortized Linear Time: Despite finding predecessor nodes by walking down subtrees, the total number of operations remains bounded by $2N$, guaranteeing strict $O(N)$ time complexity.
• Interview Essential: Highly favored in top-tier technical interviews when interviewers demand an optimal space solution for tree traversal problems.