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.

Practice

1. What is the main advantage of using Morris Traversal for inorder tree traversal compared to the traditional recursive or stack-based methods?

easy

A. It sorts the tree nodes during traversal

B. It is faster because it uses multiple threads

C. It requires the tree to be a binary search tree

D. It uses no extra space for stack or recursion, only modifies tree temporarily

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal does not use recursion or an explicit stack, instead it temporarily modifies the tree's right pointers to traverse.

2. Step 2: Compare with traditional methods

   Traditional inorder traversal uses recursion or a stack, which requires extra memory proportional to tree height.

3. Final Answer:

   It uses no extra space for stack or recursion, only modifies tree temporarily -> Option D

4. Quick Check:

   Space efficiency = No extra stack [OK]

Hint: Morris uses tree links, no stack or recursion needed [OK]

Common Mistakes:

• Thinking Morris sorts nodes
• Assuming it needs a binary search tree
• Believing it uses threads or parallelism

2. Which of the following code snippets correctly initializes the current pointer for Morris inorder traversal in C++?

easy

A. Node current = root;

B. Node* current = root;

C. Node* current = new Node(root);

D. Node current = *root;

Solution

1. Step 1: Understand pointer usage in C++ for tree traversal

   We need a pointer to traverse nodes, so current should be a pointer to Node initialized to root pointer.

2. Step 2: Analyze options

   Node* current = root; correctly declares a pointer and assigns root. Options B and D declare objects, not pointers. Node* current = new Node(root); incorrectly uses new with root pointer.

3. Final Answer:

   Node* current = root; -> Option B

4. Quick Check:

   Pointer initialization = Node* current = root [OK]

Hint: Use pointer Node* current = root for traversal [OK]

Common Mistakes:

• Declaring current as object instead of pointer
• Using new operator incorrectly
• Dereferencing root without pointer

3. Consider the following C++ code snippet implementing Morris inorder traversal on a binary tree with nodes 1, 2, 3 where 1 is root, 2 is left child, and 3 is right child. What is the output printed?

struct Node {
  int data;
  Node* left;
  Node* right;
};

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

// Tree: 1
//      / \
//     2   3

int main() {
  Node n1{1, nullptr, nullptr};
  Node n2{2, nullptr, nullptr};
  Node n3{3, nullptr, nullptr};
  n1.left = &n2;
  n1.right = &n3;
  morrisInorder(&n1);
  return 0;
}

medium

A. 3 1 2

B. 1 2 3

C. 2 1 3

D. 2 3 1

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then root, then right subtree. For tree 1 with left 2 and right 3, order is 2, 1, 3.

2. Step 2: Trace Morris traversal output

   Morris traversal prints nodes in inorder without stack. It prints 2 first (left child), then 1 (root), then 3 (right child).

3. Final Answer:

   2 1 3 -> Option C

4. Quick Check:

   Inorder output = 2 1 3 [OK]

Hint: Inorder = left, root, right; output matches 2 1 3 [OK]

Common Mistakes:

• Confusing preorder or postorder output
• Ignoring temporary link restoration
• Assuming output is sorted only for BST

4. The following code attempts Morris inorder traversal but causes an infinite loop. What is the bug?

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

medium

A. The inner while loop misses checking pre->right != current causing infinite loop

B. The current pointer is not updated after printing

C. The code does not handle nullptr root

D. The pre pointer is not initialized correctly

Solution

1. Step 1: Analyze inner while loop condition

   The inner while loop should check if pre->right is not nullptr and not equal to current to avoid infinite loop.

2. Step 2: Identify missing condition causing infinite loop

   Missing check pre->right != current causes loop to never break when pre->right points back to current, causing infinite loop.

3. Final Answer:

   The inner while loop misses checking pre->right != current causing infinite loop -> Option A

4. Quick Check:

   Loop condition must check pre->right != current [OK]

Hint: Check inner loop condition includes pre->right != current [OK]

Common Mistakes:

• Ignoring second condition in inner loop
• Forgetting to update current after printing
• Not handling empty tree

5. You want to modify Morris inorder traversal to count the number of nodes in a binary tree without using extra space or recursion. Which modification is correct?

void morrisCount(Node* root) {
  int count = 0;
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      count++;
      current = current->right;
    } else {
      Node* pre = current->left;
      while (pre->right != nullptr && pre->right != current) {
        pre = pre->right;
      }
      if (pre->right == nullptr) {
        pre->right = current;
        current = current->left;
      } else {
        pre->right = nullptr;
        count++;
        current = current->right;
      }
    }
  }
  std::cout << count << std::endl;
}

hard

A. This code correctly counts nodes using Morris traversal without extra space

B. Counting should be done only when pre->right is nullptr

C. Count variable must be global to work correctly

D. Morris traversal cannot be used to count nodes without recursion

Solution

1. Step 1: Understand counting during Morris traversal

   Count nodes when visiting them: when left is nullptr or after restoring links (pre->right == current).

2. Step 2: Verify code increments count correctly

   Code increments count in both cases correctly, so it counts all nodes without extra space or recursion.

3. Final Answer:

   This code correctly counts nodes using Morris traversal without extra space -> Option A

4. Quick Check:

   Count increments on node visit = correct [OK]

Hint: Increment count on node visit before moving right [OK]

Common Mistakes:

• Counting only once per node visit
• Making count global unnecessarily
• Assuming Morris can't count nodes