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 space like a stack or recursion. It temporarily changes the tree structure by creating links to predecessor nodes, allowing traversal without extra memory. After visiting nodes, it restores the tree to its original form. This method helps save memory while still visiting nodes in the correct order.

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 devices. Morris Traversal solves this by using no extra space, making it efficient and practical for memory-constrained environments. Without it, programs might run slower or crash due to memory limits 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 space-optimized tree traversals and advanced tree algorithms like threaded binary trees or tree flattening techniques.

Mental Model

Core Idea

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

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 explore without getting lost or needing a map, and then erase the arrows once done.

Binary Tree Node Structure:

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

1. Start at root.
2. If left child is null, visit node and go right.
3. Else find rightmost node in left subtree (predecessor).
4. If predecessor's right is null, link it to current node and go left.
5. If predecessor's right points to current, remove link, visit current, go right.

This creates temporary threads to predecessors to avoid stack.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Inorder Traversal

Concept: Learn the basic inorder traversal visiting left subtree, node, then right subtree.

Inorder traversal means visiting nodes in this order: left child, current node, right child. For example, in a binary tree: 2 / \ 1 3 The inorder traversal visits nodes as 1, 2, 3. Usually done with recursion or a stack to remember nodes.

Result

Nodes visited in sorted order for binary search trees: 1 -> 2 -> 3 -> null

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

2

Foundation

Limitations of Stack and Recursion

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

Recursive inorder traversal uses the call stack to remember nodes. Iterative traversal uses an explicit stack. Both need extra space: - For a balanced tree of height h, space is O(h). - For skewed trees, space can be O(n). This extra memory can be costly for large trees or limited memory.

Result

Traversal works but uses extra memory which can be large in worst cases.

Knowing the memory cost motivates finding traversal methods without extra space.

3

Intermediate

Finding the Inorder Predecessor

🤔Before reading on: do you think the inorder predecessor is always the left child? Commit to yes or no.

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

For a current node, its inorder predecessor is the rightmost node in its left subtree. To find it: - Start at left child. - Move right repeatedly until right child is null or points back to current node. This predecessor helps create temporary links for traversal.

Result

You can locate the predecessor node to create a temporary thread.

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

4

Intermediate

Creating and Removing Temporary Threads

🤔Before reading on: do you think temporary links are permanent changes to the tree? Commit to yes or no.

Concept: Learn how Morris Traversal creates temporary right links from predecessor to current node and removes them after use.

When predecessor's right is null, set it to current node (thread creation). This allows returning to current after left subtree. When predecessor's right points to current, remove the link (set to null) and visit current node. This process avoids using stack or recursion.

Result

Traversal visits nodes in order without extra memory and restores tree structure.

Knowing that threads are temporary and reversible prevents tree corruption.

5

Intermediate

Implementing Morris Traversal Algorithm

🤔Before reading on: do you think Morris Traversal visits nodes in preorder or inorder? Commit to your answer.

Concept: Combine predecessor finding and thread creation/removal to traverse inorder without stack or recursion.

Algorithm steps: 1. Initialize current as root. 2. While current is not null: a. If current.left is null, visit current and move to current.right. b. Else find predecessor in left subtree. i. If predecessor.right is null, set it to current, move current to current.left. ii. Else set predecessor.right to null, visit current, move current to current.right. This visits nodes in inorder sequence.

Result

Nodes visited in inorder: left subtree, node, right subtree without extra memory.

Combining these steps enables memory-efficient traversal preserving node order.

6

Advanced

C# Code for Morris Inorder Traversal

🤔Before reading on: do you think the code needs a stack or recursion? Commit to yes or no.

Concept: See a complete, runnable C# implementation of Morris Traversal inorder without stack.

public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { this.val = val; this.left = left; this.right = right; } } public class Solution { public void MorrisInorder(TreeNode root) { TreeNode current = root; while (current != null) { if (current.left == null) { System.Console.Write(current.val + " -> "); current = current.right; } else { TreeNode predecessor = current.left; while (predecessor.right != null && predecessor.right != current) { predecessor = predecessor.right; } if (predecessor.right == null) { predecessor.right = current; // create thread current = current.left; } else { predecessor.right = null; // remove thread System.Console.Write(current.val + " -> "); current = current.right; } } } System.Console.WriteLine("null"); } } // Example usage: // TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3)); // new Solution().MorrisInorder(root);

Result

Output: 1 -> 2 -> 3 -> null

Seeing the full code clarifies how temporary links replace stack usage in practice.

7

Expert

Surprising Efficiency and Tree Restoration

🤔Before reading on: do you think Morris Traversal permanently changes the tree? Commit to yes or no.

Concept: Understand how Morris Traversal restores the original tree structure and runs in O(n) time with O(1) space.

Morris Traversal creates temporary right links only to predecessor nodes and removes them immediately after use. This ensures the tree is unchanged after traversal. Each edge is visited at most twice: once to create a thread, once to remove it. Thus, time complexity is O(n) and space complexity is O(1), which is optimal for inorder traversal.

Result

Traversal completes with original tree intact and minimal memory use.

Knowing the traversal is both time and space optimal with no lasting tree changes is key for advanced use.

Under the Hood

Morris Traversal works by temporarily modifying the tree's right pointers of inorder predecessors to point back to the current node. This creates a threaded binary tree structure during traversal, allowing the algorithm to return to nodes after exploring left subtrees without a stack. When the traversal returns to a node via this thread, it removes the temporary link, restoring the original tree. This process ensures each node and edge is visited a limited number of times, achieving O(n) time and O(1) space complexity.

Why designed this way?

Traditional inorder traversal uses recursion or stacks, which require extra memory proportional to tree height. Morris Traversal was designed to eliminate this extra space by cleverly reusing the tree's null right pointers as temporary threads. This design trades temporary structural changes for memory efficiency, which is valuable in memory-constrained environments. Alternatives like threaded binary trees exist but require permanent changes; Morris Traversal restores the tree, preserving its original form.

Traversal Flow:

┌─────────────┐
│   Start     │
└─────┬───────┘
      │
      ▼
┌─────────────┐
│ current node│
└─────┬───────┘
      │
      ├─ if no left child ──▶ Visit node, move right
      │
      └─ else find predecessor
            │
            ├─ if predecessor.right is null
            │       └─ create thread, move left
            │
            └─ else
                    └─ remove thread, visit node, move right

Myth Busters - 3 Common Misconceptions

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

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

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 permanently changed may prevent using Morris Traversal in cases where tree integrity is critical.

Quick: Does Morris Traversal use extra memory like a stack? Commit yes or no.

Common Belief: Morris Traversal still uses extra memory similar to a stack or recursion.

Reality: Morris Traversal uses O(1) extra space by reusing tree pointers, avoiding stacks or recursion.

Why it matters: Misunderstanding space usage leads to missing out on Morris Traversal's memory efficiency benefits.

Quick: Is Morris Traversal faster than recursive inorder traversal? Commit yes or no.

Common Belief: Morris Traversal is always faster than recursive or stack-based inorder traversal.

Reality: Morris Traversal has the same O(n) time complexity but may be slower in practice due to pointer manipulation overhead.

Why it matters: Expecting speed gains may cause disappointment; Morris Traversal's main advantage is space, not speed.

Expert Zone

1

Morris Traversal temporarily converts the tree into a threaded binary tree during traversal but never permanently alters it.

2

The algorithm visits each edge at most twice, ensuring linear time complexity despite the extra pointer manipulations.

3

In highly unbalanced trees, Morris Traversal still maintains O(1) space, unlike recursion or stack methods that may degrade.

When NOT to use

Avoid Morris Traversal when tree modification is forbidden even temporarily, or when code simplicity and readability are priorities. Use recursive or iterative stack-based traversals instead. Also, if the tree nodes do not allow pointer changes (e.g., immutable structures), Morris Traversal is not applicable.

Production Patterns

Morris Traversal is used in embedded systems or memory-limited environments where recursion or stack usage is costly. It also appears in interview questions testing space optimization. In production, it can be combined with other tree algorithms that require inorder traversal without extra memory.

Connections

Threaded Binary Trees

Morris Traversal temporarily creates threads similar to threaded binary trees but removes them after traversal.

Understanding threaded binary trees helps grasp how Morris Traversal uses temporary links to avoid stacks.

Inorder Tree Traversal

Morris Traversal is an alternative method to perform inorder traversal without recursion or stack.

Knowing standard inorder traversal clarifies what Morris Traversal optimizes and how it preserves node visiting order.

Maze Navigation

Both involve leaving temporary markers to avoid getting lost and to return to previous points without extra memory.

Recognizing this pattern in navigation helps understand Morris Traversal's use of temporary threads to remember paths.

Common Pitfalls

#1 Not removing temporary threads after visiting predecessor.

Wrong approach:

if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
// Missing removal of thread here
System.Console.Write(current.val + " -> ");
current = current.right;
}

Correct approach:

if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null; // remove thread
System.Console.Write(current.val + " -> ");
current = current.right;
}

Root cause:

Forgetting to restore the tree causes infinite loops or corrupted tree structure.

#2 Visiting node before creating thread to predecessor.

Wrong approach:

if (current.left != null) {
System.Console.Write(current.val + " -> ");
// Then create thread
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
predecessor.right = current;
current = current.left;
}

Correct approach:

if (current.left == null) {
System.Console.Write(current.val + " -> ");
current = current.right;
} else {
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
System.Console.Write(current.val + " -> ");
current = current.right;
}
}

Root cause:

Visiting nodes too early breaks inorder sequence and traversal logic.

Key Takeaways

Morris Traversal enables inorder traversal of binary trees without using extra memory like stacks or recursion.

It works by temporarily linking each node's inorder predecessor back to the node, creating threads to return after left subtree traversal.

These temporary threads are removed immediately after use, restoring the original tree structure.

The algorithm runs in linear time and constant space, making it efficient for memory-limited environments.

Understanding predecessor nodes and careful thread management is essential to implement Morris Traversal correctly.

Practice

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

easy

A. It works only on binary search trees.

B. It is faster than all other traversal methods.

C. It uses no extra space for stack or recursion.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal uses threaded binary trees to avoid recursion or stack, so it uses O(1) extra space.

2. Step 2: Compare with other methods

   Recursive and stack-based traversals use O(h) space where h is tree height, so Morris Traversal saves memory.

3. Final Answer:

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

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris Traversal uses threading to avoid extra space [OK]

Common Mistakes:

• Thinking it is faster than recursive traversal
• Assuming it only works on BSTs
• Believing it permanently changes the tree

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

easy

A. TreeNode current = root;

B. TreeNode current = null;

C. TreeNode current = root.left;

D. TreeNode current = root.right;

Solution

1. Step 1: Identify starting point for traversal

   Morris traversal starts from the root node to cover the entire tree.

2. Step 2: Check initialization correctness

   Initializing current as root ensures traversal begins at the tree's root.

3. Final Answer:

   TreeNode current = root; -> Option A

4. Quick Check:

   Start traversal at root node [OK]

Hint: Start traversal from root node always [OK]

Common Mistakes:

• Starting from null causes no traversal
• Starting from left or right child misses nodes

3. What will be 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. 3 2 1

B. 1 2 3

C. 2 1 3

D. 1 3 2

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, root, then right subtree.

2. Step 2: Apply Morris traversal order on given tree

   Left child 1, then root 2, then right child 3 results in "1 2 3".

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Inorder = left-root-right = 1 2 3 [OK]

Hint: Inorder = left, root, right [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Misreading tree structure

4. Consider this snippet of Morris inorder traversal code in C#:

while (current != null) {
    if (current.left == null) {
        Console.Write(current.val + " ");
        current = current.right;
    } else {
        TreeNode predecessor = current.left;
        while (predecessor.right != null && predecessor.right == current) {
            predecessor = predecessor.right;
        }
        if (predecessor.right == null) {
            predecessor.right = current;
            current = current.left;
        } else {
            predecessor.right = null;
            Console.Write(current.val + " ");
            current = current.right;
        }
    }
}

What is the bug in this code?

medium

A. The code does not handle the case when current.left is null.

B. The Console.Write statements should be outside the if-else blocks.

C. The predecessor.right pointer is never reset to null, causing infinite loop.

D. The inner while loop should check predecessor.right != current instead of predecessor.right == current.

Solution

1. Step 1: Analyze inner while loop condition

   The loop should continue while predecessor.right != null && predecessor.right != current to reach the rightmost node in left subtree.

2. Step 2: Check given condition correctness

   The code uses predecessor.right == current, which fails to traverse the right chain properly, as it only continues if already threaded back.

3. Step 3: Why other options are wrong

   A: left null is handled in if. C: reset happens in else. D: print placement is correct for inorder.

4. Final Answer:

   The inner while loop should check predecessor.right != current instead of predecessor.right == current. -> Option D

5. Quick Check:

   Loop condition must be != null && != current [OK]

Hint: Check loop conditions carefully to avoid infinite loops [OK]

Common Mistakes:

• Confusing loop condition signs
• Forgetting to reset threaded pointers
• Misplacing print statements

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?

hard

A. Increment a counter each time you print a node's value during traversal.

B. Increment a counter only when you create a threaded link.

C. Increment a counter only when you remove a threaded link.

D. Increment a counter only when current.left is null.

Solution

1. Step 1: Identify when nodes are visited in Morris traversal

   Nodes are visited (printed) when current.left is null or after removing threaded link.

2. Step 2: Counting nodes correctly

   Incrementing counter when printing nodes ensures counting all nodes exactly once.

3. Step 3: Why other options fail

   Incrementing only on creating or removing threaded links misses nodes or counts duplicates.

4. Final Answer:

   Increment a counter each time you print a node's value during traversal. -> Option A

5. Quick Check:

   Count nodes when visiting them [OK]

Hint: Count nodes when printing during traversal [OK]

Common Mistakes:

• Counting on threaded link creation/removal
• Counting only left-null nodes
• Missing some nodes in count