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 order without using extra memory like a stack or recursion. It changes the tree temporarily by creating links to predecessors, allowing traversal with only constant extra space. After visiting nodes, it restores the tree to its original shape. This method is useful when memory is limited or recursion is not desired.

Why it matters

Without Morris Traversal, inorder tree traversal usually needs extra memory for a stack or recursion, which can be costly for large trees or limited memory environments. Morris Traversal solves this by using the tree's own structure to remember where to go next, saving memory and improving efficiency. Without it, some systems might run out of memory or slow down when processing big trees.

Where it fits

Before learning Morris Traversal, you should understand binary trees and basic inorder traversal using recursion or a stack. After mastering Morris Traversal, you can explore other tree traversal methods that optimize space or time, like threaded binary trees or iterative traversals with explicit stacks.

Mental Model

Core Idea

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

Think of it like...

Imagine walking through a maze where you leave temporary arrows on walls pointing back to where you came from, so you can return without getting lost or carrying a map.

Binary Tree Node Structure

       ┌───────┐
       │ Node  │
       │  val  │
       │ left  │───┐
       │ right │───┼──▶
       └───────┘   │
                   ▼
Traversal Steps:

1. For current node:
   ┌─────────────────────────────┐
   │ If no left child:            │
   │   Visit node, move right    │
   │ Else:                       │
   │   Find predecessor (rightmost│
   │   node in left subtree)      │
   │   If predecessor's right is │
   │   NULL: link it to current  │
   │   node, move left           │
   │   Else: remove link, visit  │
   │   node, move right          │
   └─────────────────────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Inorder Traversal

Concept: Learn how inorder traversal visits nodes in left-root-right order using recursion or a stack.

Inorder traversal means visiting the left child, then the current node, then the right child. Normally, this is done with recursion or a stack to remember where to return after visiting left subtree.

Result

Nodes are visited in sorted order for binary search trees.

Understanding the order of visiting nodes is essential before optimizing traversal methods.

2

Foundation

Limitations of Stack and Recursion

Concept: Recognize that recursion and stacks use extra memory proportional to tree height.

Recursion uses the call stack, and iterative traversal uses an explicit stack to remember nodes. For deep trees, this can cause high memory use or stack overflow.

Result

Traversal works but may fail or be inefficient for very large trees.

Knowing the memory cost of common traversal methods motivates finding a constant-space solution.

3

Intermediate

Finding the Predecessor Node

🤔Before reading on: do you think the predecessor is always the left child? Commit to your answer.

Concept: Learn how to find the rightmost node in the left subtree, called the predecessor.

For a node with a left child, its predecessor is the rightmost node in its left subtree. This node is visited just before the current node in inorder traversal.

Result

You can identify where to create temporary links to return after left subtree traversal.

Understanding the predecessor is key to linking nodes without extra memory.

4

Intermediate

Creating Temporary Links to Predecessor

🤔Before reading on: do you think we modify the tree permanently or temporarily? Commit to your answer.

Concept: Introduce the idea of linking the predecessor's right pointer to the current node temporarily.

If the predecessor's right pointer is NULL, set it to point to the current node. This acts like a thread to return after visiting left subtree. Later, this link is removed to restore the tree.

Result

Traversal can move left without losing track of where to return.

Temporarily modifying the tree structure allows traversal without extra memory.

5

Intermediate

Performing Morris Inorder Traversal Steps

🤔Before reading on: do you think nodes without left children are visited immediately or delayed? Commit to your answer.

Concept: Combine predecessor finding and temporary linking to traverse the tree inorder without stack or recursion.

Start at root. While current node is not NULL: - If no left child, visit node and move right. - Else find predecessor. - If predecessor's right is NULL, link it to current and move left. - Else remove link, visit node, move right.

Result

All nodes are visited in inorder sequence using only constant extra space.

This step shows the full traversal logic that avoids extra memory by reusing tree pointers.

6

Advanced

Restoring Tree Structure After Traversal

🤔Before reading on: do you think Morris Traversal leaves the tree changed or restores it? Commit to your answer.

Concept: Understand how the temporary links are removed to keep the tree unchanged after traversal.

When the traversal returns to a node via a temporary link, it removes that link before visiting the node. This ensures the tree is exactly as before after traversal finishes.

Result

The original tree structure is preserved, avoiding side effects.

Knowing the traversal cleans up after itself prevents bugs and data corruption.

7

Expert

Analyzing Time Complexity and Edge Cases

🤔Before reading on: do you think Morris Traversal always visits each node once? Commit to your answer.

Concept: Explore how Morris Traversal visits nodes multiple times but still runs in linear time, and consider edge cases like skewed trees.

Each edge is traversed at most twice: once to create a link and once to remove it. This keeps time complexity O(n). Skewed trees behave like linked lists, but traversal still works correctly.

Result

Morris Traversal is efficient and reliable even for unusual tree shapes.

Understanding traversal frequency and complexity helps optimize and trust the algorithm in production.

Under the Hood

Morris Traversal works by temporarily modifying the tree's right pointers of predecessor nodes to point back to the current node. This creates a threaded path that simulates the call stack or explicit stack used in recursion or iterative traversal. When the traversal returns to a node via this thread, it removes the link to restore the original tree. This clever use of pointers allows inorder traversal with O(1) extra space.

Why designed this way?

Traditional inorder traversal requires extra memory for recursion or stacks, which can be costly. Morris Traversal was designed to avoid this by using the tree's own structure to remember traversal paths. Alternatives like threaded binary trees existed but required permanent changes. Morris Traversal's temporary links provide a non-destructive, memory-efficient solution.

Traversal Flow:

Current Node
   │
   ▼
┌─────────────────────────────┐
│ If left child is NULL       │
│   Visit node                │
│   Move to right child       │
│ Else                       │
│   Find predecessor          │
│   ┌─────────────────────┐  │
│   │ If predecessor.right│  │
│   │ is NULL:            │  │
│   │   Link to current   │  │
│   │   Move left         │  │
│   │ Else:               │  │
│   │   Remove link       │  │
│   │   Visit node        │  │
│   │   Move right        │  │
│   └─────────────────────┘  │
└─────────────────────────────┘

Myth Busters - 4 Common Misconceptions

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

Common Belief: Morris Traversal changes the tree permanently by modifying pointers.

Reality: Morris Traversal only creates temporary links during traversal and removes them before finishing, restoring the original tree.

Why it matters: Believing the tree is changed can prevent using Morris Traversal when preservation is required, missing out on its memory benefits.

Quick: Does Morris Traversal visit each node exactly once? Commit yes or no.

Common Belief: Each node is visited only once during Morris Traversal.

Reality: Some nodes are visited twice: once when creating a link and once when removing it, but overall time remains linear.

Why it matters: Misunderstanding this can lead to incorrect assumptions about performance or cause confusion when debugging.

Quick: Can Morris Traversal be used on any binary tree, including empty or skewed? Commit yes or no.

Common Belief: Morris Traversal only works on balanced binary trees.

Reality: Morris Traversal works on all binary trees, including empty, skewed, or unbalanced trees.

Why it matters: Limiting its use to balanced trees reduces its applicability and prevents solving problems on real-world unbalanced data.

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

Common Belief: Morris Traversal uses extra memory like a stack or recursion.

Reality: Morris Traversal uses only constant extra memory by reusing tree pointers.

Why it matters: Misunderstanding memory use can lead to inefficient solutions or avoiding Morris Traversal unnecessarily.

Expert Zone

1

Morris Traversal temporarily modifies the tree but must carefully restore links to avoid corrupting the structure, which can be tricky in concurrent or multi-threaded environments.

2

The algorithm's time complexity is O(n) despite some nodes being visited twice, because each edge is traversed at most twice, a subtle but important detail for performance analysis.

3

Morris Traversal can be adapted for preorder traversal by changing when nodes are visited, showing its flexibility beyond just inorder traversal.

When NOT to use

Avoid Morris Traversal when the tree structure must remain absolutely untouched during traversal, such as in concurrent systems without locks, or when pointer modifications are forbidden. In such cases, use iterative traversal with an explicit stack or recursion.

Production Patterns

In production, Morris Traversal is used in memory-constrained environments like embedded systems or when processing very large trees where stack overflow is a risk. It is also used in interview problems to demonstrate deep understanding of tree traversal optimizations.

Connections

Threaded Binary Trees

Morris Traversal builds temporary threads similar to permanent threads in threaded binary trees.

Understanding Morris Traversal helps grasp how threaded binary trees permanently link nodes to enable efficient traversal.

Call Stack in Recursion

Morris Traversal simulates the call stack by using tree pointers instead of memory.

Knowing how recursion uses the call stack clarifies why Morris Traversal's pointer threading replaces the need for extra memory.

Maze Navigation

Both involve leaving temporary markers to avoid getting lost and to find the way back.

Recognizing this pattern in different fields shows how temporary state can replace memory in navigation problems.

Common Pitfalls

#1 Forgetting to remove the temporary link after visiting the predecessor.

Wrong approach:

if (predecessor->right == NULL) {
predecessor->right = current;
current = current->left;
} else {
// Missing removal of link here
visit(current);
current = current->right;
}

Correct approach:

if (predecessor->right == NULL) {
predecessor->right = current;
current = current->left;
} else {
predecessor->right = NULL; // Remove temporary link
visit(current);
current = current->right;
}

Root cause:

Not restoring the tree causes infinite loops or corrupted structure.

#2 Visiting nodes before creating the temporary link to predecessor.

Wrong approach:

if (current->left == NULL) {
visit(current);
current = current->right;
} else {
visit(current); // Wrong: visiting too early
predecessor = findPredecessor(current);
// ...

Correct approach:

if (current->left == NULL) {
visit(current);
current = current->right;
} else {
predecessor = findPredecessor(current);
// Create link or remove it before visiting
}

Root cause:

Visiting nodes too early breaks inorder sequence.

#3 Assuming Morris Traversal works only on binary search trees.

Wrong approach:

Using Morris Traversal only on BSTs and avoiding other binary trees.

Correct approach:

Apply Morris Traversal on any binary tree regardless of node values or order.

Root cause:

Confusing inorder traversal's sorted output on BSTs with the traversal method itself.

Key Takeaways

Morris Traversal enables inorder traversal of binary trees using only constant extra space by temporarily linking nodes to their predecessors.

It avoids recursion and stacks by cleverly modifying and restoring the tree's pointers during traversal.

Understanding how to find and use the predecessor node is essential to implementing Morris Traversal correctly.

The algorithm visits some nodes twice but still runs in linear time and restores the original tree structure after traversal.

Morris Traversal is especially useful in memory-limited environments or when recursion is not feasible.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to traditional methods?

easy

A. It only works on binary search trees

B. It is faster than all other traversal methods

C. It uses no extra space like stack or recursion

D. It requires a special tree structure

Solution

1. Step 1: Understand traditional inorder traversal space usage

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

2. Step 2: Identify Morris Traversal space usage

   Morris Traversal modifies tree links temporarily to avoid stack or recursion, using O(1) extra space.

3. Final Answer:

   It uses no extra space like stack or recursion -> Option C

4. Quick Check:

   Morris Traversal = O(1) space [OK]

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

Common Mistakes:

• Thinking Morris is faster in time complexity
• Assuming it only works on BSTs
• Believing it needs special tree nodes

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

easy

A. struct Node* current = root;

B. struct Node current = root;

C. Node* current = NULL;

D. struct Node* current = NULL;

Solution

1. Step 1: Understand pointer initialization in C for tree traversal

   We need a pointer to the root node to start traversal, so 'struct Node* current = root;' is correct.

2. Step 2: Check other options for correctness

   struct Node current = root; declares a struct variable, not a pointer, which is incorrect. Node* current = NULL; uses 'Node*' without 'struct' keyword, invalid in C. struct Node* current = NULL; initializes current to NULL, which won't start traversal.

3. Final Answer:

   struct Node* current = root; -> Option A

4. Quick Check:

   Pointer to root = struct Node* current = root; [OK]

Hint: Use pointer to root node: struct Node* current = root; [OK]

Common Mistakes:

• Using struct variable instead of pointer
• Omitting 'struct' keyword in C
• Initializing current to NULL instead of root

3. What is the output of the Morris inorder traversal on the following binary tree?

    2
   / \
  1   3

Assuming the traversal prints node values separated by spaces.

medium

A. 1 3 2

B. 1 2 3

C. 3 2 1

D. 2 1 3

Solution

1. Step 1: Understand inorder traversal order

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

2. Step 2: Apply Morris traversal logic

   Morris traversal visits nodes in inorder without stack. The output will be "1 2 3 " as it visits left child, root, then right child.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Inorder of tree = 1 2 3 [OK]

Hint: Inorder = left, root, right; output matches this order [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Forgetting spaces in output
• Misreading tree structure

4. Identify the bug in this Morris inorder traversal snippet:

while (current != NULL) {
  if (current->left == NULL) {
    printf("%d ", current->data);
    current = current->right;
  } else {
    struct Node* pre = current->left;
    while (pre->right != NULL) {
      pre = pre->right;
    }
    pre->right = current;
    current = current->left;
  }
}

medium

A. Should use recursion instead of loop

B. Missing initialization of current pointer

C. Incorrect print statement syntax

D. The inner while loop should check pre->right != current

Solution

1. Step 1: Analyze inner while loop condition

   The inner loop finds the rightmost node in left subtree. It should stop if pre->right points back to current to avoid infinite loop.

2. Step 2: Identify correct condition

   The condition must be 'pre->right != NULL && pre->right != current' to detect if thread already exists and avoid infinite loop.

3. Final Answer:

   The inner while loop should check pre->right != current -> Option D

4. Quick Check:

   Loop condition must detect thread to current [OK]

Hint: Check thread link to current in inner loop condition [OK]

Common Mistakes:

• Not checking pre->right != current causes infinite loop
• Forgetting to restore tree links after traversal
• Confusing recursion with Morris traversal

5. Given a binary tree where some nodes have only left children, how does Morris inorder traversal handle these nodes without using stack or recursion?

hard

A. It creates temporary threads from rightmost left child back to current node

B. It skips nodes without right children

C. It uses a stack internally to track nodes

D. It converts the tree into a linked list first

Solution

1. Step 1: Understand Morris traversal threading

   Morris traversal creates temporary links (threads) from the rightmost node of left subtree back to the current node to remember where to return.

2. Step 2: Apply to nodes with only left children

   For nodes with only left children, it finds the rightmost node in left subtree (which may be the left child itself) and creates a thread back to current node, enabling traversal without stack.

3. Final Answer:

   It creates temporary threads from rightmost left child back to current node -> Option A

4. Quick Check:

   Temporary threads enable traversal without stack [OK]

Hint: Threads link back to current node from left subtree's rightmost node [OK]

Common Mistakes:

• Assuming nodes without right children are skipped
• Thinking Morris uses stack internally
• Believing tree is converted to linked list