Morris Traversal Inorder Without Stack in DSA C++

Mental Model

We visit nodes in order without using extra memory by temporarily changing tree links to remember where to return.

Analogy: Imagine walking through a maze where you leave temporary signs on walls to find your way back without carrying a map or notes.

    4
   / \
  2   5
 / \
1   3

No extra stack or recursion, just clever rewiring of pointers.

Dry Run Walkthrough

Input: Binary tree: 4 -> 2, 5, 1, 3 (root 4 with left child 2 and right child 5; 2 has children 1 and 3).

Goal: Print nodes in inorder (1 2 3 4 5) without using stack or recursion by modifying pointers temporarily.

Step 1: Start at root 4, find predecessor of 4 in left subtree (rightmost node in left subtree).

4 ↑ -> 2 -> 5
2 -> 1 -> 3
Predecessor of 4 is 3 (right child of 2).

Why: We need to find where to return after visiting left subtree.

Step 2: Make 3's right pointer point to 4 (threading), move current to left child 2.

4 -> 2 ↑ -> 5
2 -> 1 -> 3 -> 4 (thread)
Temporary link created to return to 4.

Why: This thread helps us come back to 4 after finishing left subtree.

Step 3: At 2, find predecessor in left subtree (rightmost node in left subtree).

4 -> 2 ↑ -> 5
2 -> 1 -> 3 -> 4 (thread)
Predecessor of 2 is 1 (left child has no right child).

Why: We want to visit left subtree of 2 first.

Step 4: 1 has no left child, print 1 and move to right child (which is null).

4 -> 2 -> 5
2 -> 1 ↑ -> 3 -> 4 (thread)
Printed 1.

Why: Leaf node with no left subtree, so print and move on.

Step 5: Back at 2 via thread from 1, remove thread, print 2, move to right child 3.

4 -> 2 ↑ -> 5
2 -> 1 -> 3 -> 4 (thread removed)
Printed 2.

Why: Finished left subtree of 2, now print 2 and go right.

Step 6: 3 has no left child, print 3 and move to right child (which points to 4 via thread).

4 -> 2 -> 5
2 -> 1 -> 3 ↑ -> 4
Printed 3.

Why: Leaf node, print and follow thread back to 4.

Step 7: Back at 4 via thread from 3, remove thread, print 4, move to right child 5.

4 ↑ -> 2 -> 5
2 -> 1 -> 3
Printed 4.

Why: Finished left subtree of 4, now print 4 and go right.

Step 8: 5 has no left child, print 5 and move to right child null (end).

4 -> 2 -> 5 ↑
2 -> 1 -> 3
Printed 5.

Why: Leaf node, print and traversal ends.

Result:

1 -> 2 -> 3 -> 4 -> 5 -> null
Printed inorder traversal without stack or recursion.

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void morrisInorder(Node* root) {
    Node* curr = root;
    while (curr != nullptr) {
        if (curr->left == nullptr) {
            cout << curr->val << " ";
            curr = curr->right; // move to right child when no left subtree
        } else {
            Node* pred = curr->left;
            while (pred->right != nullptr && pred->right != curr) {
                pred = pred->right; // find rightmost node in left subtree
            }
            if (pred->right == nullptr) {
                pred->right = curr; // create thread to return
                curr = curr->left; // move to left child
            } else {
                pred->right = nullptr; // remove thread
                cout << curr->val << " ";
                curr = curr->right; // move to right child
            }
        }
    }
}

int main() {
    Node* root = new Node(4);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(1);
    root->left->right = new Node(3);

    morrisInorder(root);
    cout << "\n";
    return 0;
}

while (curr != nullptr) {

iterate until all nodes are processed

if (curr->left == nullptr) {

if no left subtree, print current and move right

curr = curr->right; // move to right child when no left subtree

advance to next node on right

Node* pred = curr->left;

find predecessor in left subtree

while (pred->right != nullptr && pred->right != curr) { pred = pred->right; }

find rightmost node in left subtree or existing thread

if (pred->right == nullptr) { pred->right = curr; curr = curr->left; }

create thread and move left

else { pred->right = nullptr; cout << curr->val << " "; curr = curr->right; }

remove thread, print current, move right

Output

1 2 3 4 5 

Complexity Analysis

Time: O(n) because each edge is visited at most twice during threading and removal

Space: O(1) because no extra stack or recursion is used, only pointers are changed temporarily

vs Alternative: Compared to recursion or stack-based inorder which use O(h) space, Morris traversal uses constant space by modifying tree pointers temporarily.

Edge Cases

Empty tree (root is nullptr)

No output, traversal ends immediately

DSA C++

while (curr != nullptr) {

Tree with single node

Prints the single node value correctly

DSA C++

if (curr->left == nullptr) {

Tree with no left children (all right skewed)

Prints nodes in order by moving right pointers only

DSA C++

if (curr->left == nullptr) {

When to Use This Pattern

When asked to do inorder traversal without extra memory like stack or recursion, think of Morris Traversal which uses temporary pointer threading to remember return paths.

Common Mistakes

Mistake: Not removing the temporary thread after visiting left subtree, causing infinite loops.
Fix: Always reset predecessor's right pointer to nullptr after printing current node.

Mistake: Not checking if predecessor's right pointer already points to current node before creating thread.
Fix: Check if pred->right == nullptr before creating thread; if pred->right == curr, remove thread instead.

Summary

Prints inorder traversal of a binary tree without using stack or recursion by temporarily modifying pointers.

Use when memory is limited and you want to avoid recursion or stack overhead for inorder traversal.

The key insight is to create temporary threads from predecessor nodes back to current nodes to remember return paths.