Morris Traversal is one of the most brilliant algorithms in computer science. It solves the exact constraint you’re facing: how do you traverse a tree without spending any extra memory on a stack?

1. The Core Secret: Threaded Binary Trees

When you are at a node and go deep into its left subtree, how do you get back up to the node without a parent pointer or call stack? Normally, you need a stack to remember the return path.

J. H. Morris realized something clever: in every binary tree, about half of all pointers are NULL! Every leaf node has a null right child that is sitting there doing nothing.

Morris repurposes these unused null pointers as temporary bridge wires (called “threads”) back to the inorder successor:

1. Find the node’s inorder predecessor (the rightmost node in the left subtree).
2. If its right pointer is null, point it back to the current node: predecessor->right = current. Then move current = current->left.
3. If its right pointer is already pointing to current, that means you have already finished visiting the left subtree! You print/record current->val, restore the pointer to null (repairing the tree), and move current = current->right!

When the algorithm finishes, the tree is 100% restored to its original state. Zero memory allocated, zero permanent mutations!

Clean C++20 Morris Inorder Traversal

#include <vector>
#include <cstdint>

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

std::vector<int> morrisInorderTraversal(TreeNode* root) {
    std::vector<int> result;
    TreeNode* curr = root;

    while (curr != nullptr) {
        if (curr->left == nullptr) {
            // Case 1: No left child, visit this node and move right
            result.push_back(curr->val);
            curr = curr->right;
        } else {
            // Case 2: Find inorder predecessor (rightmost in left subtree)
            TreeNode* pred = curr->left;
            while (pred->right != nullptr && pred->right != curr) {
                pred = pred->right;
            }

            if (pred->right == nullptr) {
                // First time visiting: create temporary thread
                pred->right = curr;
                curr = curr->left;
            } else {
                // Second time visiting: restore tree and visit curr
                pred->right = nullptr;
                result.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return result;
}

Complexity & Trade-offs

• Time Complexity: O(N). Even though we search for predecessors, each edge in the tree is traversed at most 3 times (once to find predecessor, once to create thread, once to remove thread). 3 * (N - 1) = O(N).
• Space Complexity: O(1) auxiliary space. Just two pointers (curr and pred). No call stack, no heap allocations.
• Thread-Safety Warning: Because Morris Traversal temporarily mutates right pointers during execution, it is not safe for concurrent readers on the same tree instance. If multiple threads read the tree simultaneously, use standard recursive DFS with a large stack or an explicit thread-local queue.