Why Morris Traversal Inorder Without Stack in DSA C++?

The Big Idea

Discover how to walk through a tree without carrying extra memory or getting lost!

The Scenario

Imagine you want to walk through a maze (a tree) and note down every room (node) you visit in order. Without a map or a helper (stack), you try to remember every turn you took. It quickly becomes confusing and you might get lost or repeat rooms.

The Problem

Using a stack or recursion to remember your path takes extra memory and can slow you down. If the maze is huge, carrying this memory is heavy and inefficient. Also, managing this memory manually can cause mistakes and crashes.

The Solution

Morris Traversal cleverly uses the maze itself to mark your path temporarily. It creates small shortcuts (temporary links) so you can walk through all rooms in order without extra memory. After visiting, it cleans up these shortcuts, leaving the maze unchanged.

Before vs After

✗ Before

void inorderTraversal(Node* root) {
    std::stack<Node*> nodeStack;
    Node* current = root;
    while (current != nullptr || !nodeStack.empty()) {
        while (current != nullptr) {
            nodeStack.push(current);
            current = current->left;
        }
        current = nodeStack.top();
        nodeStack.pop();
        std::cout << current->data << " ";
        current = current->right;
    }
}

✓ After

void morrisInorderTraversal(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                std::cout << current->data << " ";
                current = current->right;
            }
        }
    }
}

What It Enables

This method enables you to traverse a binary tree in order using only constant extra space, making it efficient for large trees or memory-limited environments.

Real Life Example

Think of exploring a large library where you want to read every book in order without carrying a big notebook or asking for help. Morris Traversal is like using bookmarks inside the books themselves to remember where you left off.

Key Takeaways

Morris Traversal avoids extra memory by temporarily modifying the tree.

It visits nodes in inorder sequence without stack or recursion.

After traversal, the tree structure is restored to original.