Morris Traversal Inorder Without Stack in DSA C++ - Deep Dive

Overview - Morris Traversal Inorder Without Stack

What is it?

Morris Traversal is a way to visit all nodes of a binary tree in inorder sequence without using extra memory like a stack or recursion. It temporarily changes the tree structure by creating links to predecessors, allowing traversal with constant space. After visiting nodes, it restores the tree to its original form. This method is efficient for memory-limited environments.

Why it matters

Without Morris Traversal, inorder tree traversal usually requires extra memory for a stack or recursion, which can be costly for large trees or limited memory devices. Morris Traversal solves this by using no extra space, making it useful in embedded systems or when memory is tight. Without it, programs might run slower or crash due to memory limits.

Where it fits

Before learning Morris Traversal, you should understand binary trees, inorder traversal, and recursion or stack-based traversal methods. After mastering Morris Traversal, you can explore other tree traversal optimizations and advanced tree algorithms like threaded binary trees or balanced tree structures.

Mental Model

Core Idea

Morris Traversal visits nodes by temporarily linking each node's inorder predecessor back to it, enabling traversal without extra memory and restoring the tree afterward.

Think of it like...

Imagine walking through a maze where you leave temporary breadcrumbs to mark your path back without carrying a map or notes. Once you finish, you pick up all breadcrumbs, leaving the maze unchanged.

Binary Tree Node Structure:

       [Current]
          |
          v
   [Left Subtree] <-- temporary link (thread) -- [Inorder Predecessor]

Traversal Steps:
1. If current node has no left child, visit it and move right.
2. Else, find inorder predecessor in left subtree.
3. If predecessor's right is null, link it to current and move left.
4. If predecessor's right points to current, remove link, visit current, move right.

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Inorder Traversal

Concept: Learn the basic inorder traversal using recursion or stack to visit nodes in left-root-right order.

Inorder traversal visits the left child, then the current node, then the right child. For example, for a node: void inorder(Node* root) { if (!root) return; inorder(root->left); visit(root); inorder(root->right); } This uses the call stack to remember nodes.

Result

Nodes are visited in sorted order for binary search trees, but recursion uses extra memory proportional to tree height.

Understanding standard inorder traversal sets the stage to appreciate how Morris Traversal avoids extra memory by changing the tree temporarily.

2

Foundation

Role of Stack in Traditional Traversal

Concept: Recognize why a stack or recursion is needed to remember nodes when traversing back up the tree.

When visiting a node's left subtree, we must remember to come back to the node before going right. A stack stores these nodes: stack s; Node* curr = root; while (curr || !s.empty()) { while (curr) { s.push(curr); curr = curr->left; } curr = s.top(); s.pop(); visit(curr); curr = curr->right; } This uses O(h) memory where h is tree height.

Result

Traversal works correctly but uses extra space proportional to tree height.

Knowing the stack's role clarifies why Morris Traversal's no-stack approach is clever and memory efficient.

3

Intermediate

Finding Inorder Predecessor in Left Subtree

Concept: Learn to find the rightmost node in the left subtree, called the inorder predecessor, which helps create temporary links.

For a node with a left child, its inorder predecessor is the rightmost node in its left subtree: Node* pred = curr->left; while (pred->right && pred->right != curr) { pred = pred->right; } This node is visited just before the current node in inorder traversal.

Result

You can identify where to create or remove temporary links to traverse without stack.

Understanding the inorder predecessor is key to Morris Traversal's mechanism of threading the tree.

4

Intermediate

Creating and Removing Temporary Threads

🤔Before reading on: do you think temporary links in Morris Traversal permanently change the tree structure? Commit to yes or no.

Concept: Morris Traversal creates temporary right links from the inorder predecessor back to the current node, then removes them after visiting.

If predecessor's right is null, set it to current node (thread creation) and move current to left child. If predecessor's right points to current, remove the thread (set to null), visit current, and move right. This allows returning to current node without stack or recursion.

Result

Traversal visits all nodes in inorder without extra memory and restores the tree to original shape.

Knowing threads are temporary and removed ensures the tree remains unchanged after traversal, which is crucial for correctness.

5

Advanced

Implementing Morris Inorder Traversal in C++

🤔Before reading on: do you think Morris Traversal is faster, slower, or the same speed as stack-based traversal? Commit to your answer.

Concept: Combine all ideas into a complete C++ function that performs Morris inorder traversal without stack or recursion.

void morrisInorder(Node* root) { Node* curr = root; while (curr) { if (!curr->left) { visit(curr); curr = curr->right; } else { Node* pred = curr->left; while (pred->right && pred->right != curr) { pred = pred->right; } if (!pred->right) { pred->right = curr; // create thread curr = curr->left; } else { pred->right = nullptr; // remove thread visit(curr); curr = curr->right; } } } } void visit(Node* node) { std::cout << node->val << " -> "; }

Result

Nodes are printed in inorder sequence without using extra memory beyond variables.

Understanding the full implementation reveals how temporary links replace stack memory, achieving O(1) space traversal.

6

Expert

Performance and Limitations of Morris Traversal

🤔Before reading on: do you think Morris Traversal always outperforms stack-based traversal in speed? Commit to yes or no.

Concept: Analyze Morris Traversal's time complexity, side effects, and when it might be less efficient or unsuitable.

Morris Traversal runs in O(n) time but may visit some nodes twice due to threading. It uses O(1) space but modifies the tree temporarily, which can be risky if the tree is shared or immutable. Also, it can be slower in practice due to extra pointer changes. It is not suitable for trees where modification is forbidden or in concurrent environments.

Result

Morris Traversal is memory efficient but may trade off speed and safety in some cases.

Knowing Morris Traversal's tradeoffs helps decide when to use it versus traditional methods.

Under the Hood

Morris Traversal works by exploiting the tree's null right pointers in inorder predecessors to create temporary threads back to the current node. This threading simulates the call stack or explicit stack used in recursion or iterative traversal. When the traversal returns to a node via a thread, it removes the thread to restore the original tree structure. This process allows visiting nodes in inorder without extra memory allocation.

Why designed this way?

The method was designed to reduce memory usage during inorder traversal by avoiding stack or recursion overhead. Traditional traversals require remembering the path back to nodes, which uses extra space. Morris Traversal cleverly uses the tree's own structure to remember this path temporarily, balancing space efficiency with a slight increase in pointer manipulation complexity.

Traversal Flow:

[Current Node]
    |
    v
+-------------------+
| Has Left Child?   |
+-------------------+
       |Yes                 |No
       v                    v
Find Inorder Predecessor   Visit Current
       |                    |
       v                    v
+-------------------+   Move Right
| Predecessor Right |
| is NULL?          |
+-------------------+
       |Yes                 |No
       v                    v
Create Thread to Current  Remove Thread
Move Current Left         Visit Current
                          Move Current Right

Myth Busters - 4 Common Misconceptions

Quick: Does Morris Traversal permanently change the tree structure? Commit to yes or no.

Common Belief: Morris Traversal permanently modifies the tree by adding extra links.

Reality: Morris Traversal only creates temporary links (threads) during traversal and removes them before finishing, restoring the tree to its original form.

Why it matters: Believing the tree is permanently changed may prevent using Morris Traversal in cases where tree integrity is critical, missing out on its memory benefits.

Quick: Is Morris Traversal always faster than stack-based traversal? Commit to yes or no.

Common Belief: Morris Traversal is always faster because it uses no extra memory.

Reality: Morris Traversal can be slower due to extra pointer manipulations and visiting some nodes twice, despite using less memory.

Why it matters: Assuming Morris Traversal is always faster may lead to poor performance choices in time-critical applications.

Quick: Can Morris Traversal be safely used on immutable or shared trees? Commit to yes or no.

Common Belief: Morris Traversal works on any binary tree without restrictions.

Reality: Morris Traversal modifies pointers temporarily, so it is unsafe for immutable or concurrently accessed trees.

Why it matters: Using Morris Traversal on such trees can cause data corruption or crashes.

Quick: Does Morris Traversal require extra memory proportional to tree height? Commit to yes or no.

Common Belief: Morris Traversal still needs O(h) extra memory like stack-based traversal.

Reality: Morris Traversal uses O(1) extra memory by reusing tree pointers for threading.

Why it matters: Misunderstanding space complexity may cause learners to overlook Morris Traversal's main advantage.

Expert Zone

1

Morris Traversal's temporary threads can cause subtle bugs if interrupted mid-traversal, so it is important to ensure traversal completes or handles interruptions safely.

2

The method assumes binary trees with mutable pointers; applying it to other tree types or immutable structures requires adaptations or is impossible.

3

In some cases, Morris Traversal can be combined with other tree algorithms to optimize memory usage, but this requires careful pointer management to avoid conflicts.

When NOT to use

Avoid Morris Traversal when working with immutable trees, concurrent environments, or when pointer modifications are forbidden. Use traditional recursive or stack-based traversals in these cases. Also, if traversal speed is critical and memory is sufficient, stack-based methods may be preferable.

Production Patterns

Morris Traversal is used in embedded systems or memory-constrained devices where recursion or stack usage is costly. It also appears in interview problems to test understanding of tree traversal optimizations. In production, it is often combined with careful error handling to ensure tree integrity.

Connections

Threaded Binary Trees

Morris Traversal uses temporary threading similar to threaded binary trees, which permanently store threads for traversal.

Understanding Morris Traversal helps grasp how threaded binary trees maintain traversal paths without stacks, but with permanent threads.

Call Stack in Recursion

Morris Traversal simulates the call stack by using tree pointers instead of memory, achieving the same traversal order without extra space.

Recognizing this connection clarifies how recursion remembers paths and how Morris Traversal replaces that memory with pointer manipulation.

Breadcrumb Navigation in Web Browsers

Both use temporary markers to remember paths for easy backtracking without storing full history externally.

This cross-domain link shows how temporary markers can replace memory-heavy tracking in navigation, whether in trees or user interfaces.

Common Pitfalls

#1 Not removing temporary threads after visiting nodes.

Wrong approach:

if (pred->right == nullptr) {
pred->right = curr; // create thread
curr = curr->left;
} else {
visit(curr);
curr = curr->right; // forgot to remove thread
}

Correct approach:

if (pred->right == nullptr) {
pred->right = curr; // create thread
curr = curr->left;
} else {
pred->right = nullptr; // remove thread
visit(curr);
curr = curr->right;
}

Root cause:

Forgetting to remove threads leaves the tree modified, causing infinite loops or incorrect traversal.

#2 Visiting nodes before creating threads, breaking inorder order.

Wrong approach:

if (curr->left) {
visit(curr); // visited too early
curr = curr->left;
} else {
visit(curr);
curr = curr->right;
}

Correct approach:

if (!curr->left) {
visit(curr);
curr = curr->right;
} else {
// create or remove threads as needed
}

Root cause:

Misunderstanding traversal order leads to visiting nodes out of inorder sequence.

#3 Using Morris Traversal on immutable or shared trees.

Wrong approach:

// Attempting Morris Traversal on const or shared tree
const Node* root = ...;
morrisInorder(root); // modifies pointers illegally

Correct approach:

// Use stack-based traversal for immutable trees
void inorder(const Node* root) {
if (!root) return;
inorder(root->left);
visit(root);
inorder(root->right);
}

Root cause:

Not recognizing pointer modification requirement causes unsafe behavior or compilation errors.

Key Takeaways

Morris Traversal enables inorder traversal of binary trees using O(1) extra space by temporarily modifying tree pointers.

It works by creating and removing temporary threads from inorder predecessors back to current nodes, simulating stack behavior.

This method preserves the original tree structure by removing all temporary links after traversal.

Morris Traversal trades off some speed and complexity for memory efficiency and is unsuitable for immutable or concurrent trees.

Understanding Morris Traversal deepens insight into tree traversal mechanics and pointer manipulation techniques.

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