Morris Traversal Inorder Without Stack in DSA Java - 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 to remember where to go next. After visiting, 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 the tree itself to keep track of progress, saving space and making traversal efficient. This is important in systems where memory is limited or performance matters.

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 and advanced tree algorithms that optimize space and time.

Mental Model

Core Idea

Morris Traversal visits nodes by temporarily linking a node's predecessor back to it, allowing 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:

       [Current Node]
          /      \
   [Left Child]  [Right Child]

Morris Traversal Steps:

1. If left child is null, visit current node and move right.
2. Else, find rightmost node in left subtree (predecessor).
3. If predecessor's right is null, set it to current node (create thread), move left.
4. If predecessor's right points to current node, remove thread, visit current node, move right.

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 tree with root 2, left child 1, right child 3, the inorder sequence is 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.

Recursion uses the call stack to remember nodes, which can grow to the tree's height. Similarly, iterative traversal uses an explicit stack. This extra memory can be large for deep trees, causing inefficiency or crashes.

Result

Traversal works but uses O(h) extra space, where h is tree height.

Knowing the memory cost motivates finding traversal methods that use less space.

3

Intermediate

Introducing Threaded Binary Trees Concept

Concept: Use unused right pointers in the tree to create temporary links (threads) to predecessors.

In a threaded binary tree, some null right pointers are used to point back to the node's inorder successor or predecessor. This helps traversal without extra memory by following these threads instead of a stack.

Result

Tree structure temporarily changes to include threads, enabling traversal without stack.

Using the tree's own pointers cleverly avoids external memory use.

4

Intermediate

Finding Predecessor and Creating Threads

🤔Before reading on: Do you think the predecessor is always the left child or the rightmost node in the left subtree? Commit to your answer.

Concept: Identify the rightmost node in the left subtree as the predecessor to create a thread back to the current node.

For each node with a left child, find its inorder predecessor by going to the left child and then as far right as possible. If the predecessor's right pointer is null, set it to current node (thread). This marks a path back after left subtree is done.

Result

Threads allow returning to nodes without stack or recursion.

Knowing how to find and use the predecessor is key to Morris Traversal's space efficiency.

5

Intermediate

Restoring Tree and Visiting Nodes

🤔Before reading on: When you find a thread back to the current node, should you visit the node before or after removing the thread? Commit to your answer.

Concept: Remove threads after visiting nodes to restore original tree structure.

When a thread points back to the current node, it means left subtree is fully visited. Remove the thread, visit the current node, then move to the right child. This ensures the tree remains unchanged after traversal.

Result

Tree structure is restored and nodes are visited in correct order.

Restoring the tree prevents side effects and keeps data integrity.

6

Advanced

Implementing Morris Traversal in Java

🤔Before reading on: Do you think Morris Traversal requires extra variables besides current and predecessor pointers? Commit to your answer.

Concept: Write complete Java code to perform Morris inorder traversal without stack or recursion.

```java class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } public class MorrisTraversal { public static void morrisInorder(TreeNode root) { TreeNode current = root; while (current != null) { if (current.left == null) { System.out.print(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.out.print(current.val + " -> "); current = current.right; } } } System.out.print("null\n"); } public static void main(String[] args) { TreeNode root = new TreeNode(2); root.left = new TreeNode(1); root.right = new TreeNode(3); morrisInorder(root); } } ```

Result

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

Implementing Morris Traversal shows how temporary threads replace stack usage, achieving O(1) space traversal.

7

Expert

Performance and Edge Cases of Morris Traversal

🤔Before reading on: Does Morris Traversal always run in O(n) time even with many threads created and removed? Commit to your answer.

Concept: Analyze time complexity and behavior on skewed or large trees.

Morris Traversal visits each node at most twice: once to create a thread and once to remove it. This guarantees O(n) time. However, it modifies the tree temporarily, which may not be allowed in some contexts. Also, it handles skewed trees gracefully without extra space.

Result

Traversal completes in linear time with constant space, restoring tree fully.

Understanding time and space tradeoffs helps decide when Morris Traversal is practical.

Under the Hood

Morris Traversal works by temporarily changing the tree's right pointers of inorder predecessors to point back to the current node. This creates a threaded link that acts like a bookmark. When the traversal returns to the current node via this thread, it knows the left subtree is done and can visit the node and move right. After visiting, it removes the thread to restore the tree. This avoids using a stack or recursion by encoding traversal state inside the tree itself.

Why designed this way?

Traditional inorder traversal uses extra memory for stacks or recursion, which can be costly. Morris Traversal was designed to use the tree's null pointers as temporary links to save space. This approach trades temporary tree modification for memory efficiency. Alternatives like threaded binary trees existed but Morris Traversal applies this idea dynamically without permanent changes.

Traversal Flow:

[Current Node]
    |
    v
[Check Left Child]
    |
    +-- No --> Visit Node --> Move Right
    |
    +-- Yes --> Find Predecessor
                  |
                  v
          [Predecessor Right]
             |
             +-- Null --> Set Thread to Current --> Move Left
             |
             +-- Points to Current --> Remove Thread --> Visit Node --> Move Right

Myth Busters - 3 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 threads.

Reality: Morris Traversal only temporarily modifies the tree and restores it fully after traversal.

Why it matters: If you assume permanent changes, you might avoid Morris Traversal unnecessarily or worry about data corruption.

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

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

Reality: Morris Traversal uses O(1) space but may be slower due to extra pointer changes and checks.

Why it matters: Choosing Morris Traversal blindly for speed can lead to worse performance in some cases.

Quick: Does Morris Traversal work on all binary trees including those with parent pointers? Commit to yes or no.

Common Belief: Morris Traversal works on any binary tree regardless of extra pointers.

Reality: Morris Traversal relies on null right pointers to create threads; trees with parent pointers or non-null right pointers may break the method.

Why it matters: Applying Morris Traversal to incompatible trees can cause incorrect traversal or crashes.

Expert Zone

1

Morris Traversal can be adapted for preorder traversal by visiting nodes before creating threads, but this subtle change affects the order and requires careful implementation.

2

In concurrent or multi-threaded environments, temporarily modifying tree pointers is unsafe without locks, limiting Morris Traversal's use.

3

Morris Traversal's pointer changes can interfere with debugging or tools that expect immutable tree structures during traversal.

When NOT to use

Avoid Morris Traversal when tree modification is forbidden, such as in immutable data structures or when concurrent access occurs. Use recursive or stack-based traversal instead. Also, if simplicity and readability are priorities over memory, traditional methods are better.

Production Patterns

Morris Traversal is used in embedded systems or memory-constrained environments where recursion or stack use is expensive. It also appears in interview problems testing space optimization. In production, it is less common due to tree modification risks but valuable for specialized low-memory algorithms.

Connections

Threaded Binary Trees

Morris Traversal dynamically creates temporary threads similar to the permanent threads in threaded binary trees.

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

Inorder Tree Traversal

Morris Traversal is an alternative method to perform inorder traversal without extra memory.

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

Maze Navigation

Both Morris Traversal and maze navigation use temporary markers to avoid getting lost without external memory.

Recognizing this pattern across domains shows how temporary state encoding inside a structure can replace external memory.

Common Pitfalls

#1 Not removing threads after visiting nodes, leaving the tree modified.

Wrong approach:

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

Correct approach:

if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null; // Remove thread
System.out.print(current.val + " -> ");
current = current.right;
}

Root cause:

Forgetting to restore the tree causes permanent pointer changes and incorrect tree structure.

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

Wrong approach:

if (current.left == null) {
System.out.print(current.val + " -> ");
current = current.right;
} else {
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
System.out.print(current.val + " -> "); // Visiting too early
if (predecessor.right == null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
current = current.right;
}
}

Correct approach:

if (current.left == null) {
System.out.print(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.out.print(current.val + " -> ");
current = current.right;
}
}

Root cause:

Visiting nodes too early breaks the inorder property of left-node-right.

#3 Assuming Morris Traversal works on trees with all right pointers non-null.

Wrong approach:

Using Morris Traversal on a tree where no right pointers are null, so threads cannot be created.

Correct approach:

Use stack or recursion traversal for trees without null right pointers.

Root cause:

Morris Traversal relies on null right pointers to create threads; without them, it fails.

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 threads from a node's inorder predecessor back to the node, avoiding stacks or recursion.

The tree is fully restored after traversal, preserving its original structure and data.

While memory efficient, Morris Traversal may be slower and is unsuitable when tree modification is forbidden or unsafe.

Understanding Morris Traversal deepens knowledge of tree traversal techniques and pointer manipulation.

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 requires the tree to be balanced

B. It is faster than all other traversal methods

C. It only works on binary search trees

D. It uses no extra space for stack or recursion

Solution

1. Step 1: Understand Morris Traversal space usage

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

2. Step 2: Compare with traditional methods

   Traditional inorder traversal uses recursion or stack which require O(h) space, where h is tree height.

3. Final Answer:

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

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris uses threaded links to avoid stack [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Assuming it only works on BSTs
• Believing it requires balanced trees

2. Which of the following code snippets correctly creates the temporary thread link in Morris Traversal inorder method?

easy

A. current.right = predecessor;

B. current.left = predecessor;

C. predecessor.right = current;

D. predecessor.left = current;

Solution

1. Step 1: Identify the thread link direction

   In Morris Traversal, the right child of the inorder predecessor is linked to current node to create a thread.

2. Step 2: Match with code snippet

   The correct assignment is predecessor.right = current; to create the temporary link.

3. Final Answer:

   predecessor.right = current; -> Option C

4. Quick Check:

   Thread link = predecessor.right = current [OK]

Hint: Thread link always sets predecessor.right to current [OK]

Common Mistakes:

• Assigning current.left to predecessor instead
• Using predecessor.left instead of right
• Confusing current.right with predecessor.right

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

    2
   / \
  1   3

medium

A. [1, 2, 3]

B. [2, 1, 3]

C. [3, 2, 1]

D. [1, 3, 2]

Solution

1. Step 1: Perform inorder traversal manually

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

2. Step 2: List nodes in inorder

   Nodes visited in order: 1, 2, 3.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Confusing preorder or postorder with inorder
• Mixing up left and right child order
• Assuming Morris changes traversal order

4. Consider this buggy snippet from a Morris inorder traversal implementation:

while (current != null) {
  if (current.left == null) {
    System.out.print(current.val + " ");
    current = current.right;
  } else {
    TreeNode predecessor = current.left;
    while (predecessor.right != null) {
      predecessor = predecessor.right;
    }
    predecessor.right = current;
    current = current.left;
  }
}

What is the main bug causing an infinite loop?

medium

A. Not printing current.val when left is not null

B. Not checking if predecessor.right == current before linking

C. Not moving current to current.right when left is null

D. Not initializing predecessor correctly

Solution

1. Step 1: Identify missing condition in inner loop

   The inner while loop should stop if predecessor.right == current to avoid infinite loop.

2. Step 2: Explain infinite loop cause

   Without checking predecessor.right == current, the loop never breaks and keeps moving right, causing infinite loop.

3. Final Answer:

   Not checking if predecessor.right == current before linking -> Option B

4. Quick Check:

   Check predecessor.right == current to break loop [OK]

Hint: Always check predecessor.right == current to avoid loops [OK]

Common Mistakes:

• Ignoring thread existence check
• Assuming printing happens in else block
• Incorrect predecessor initialization

5. Given a binary tree where some nodes have only left children, how does Morris Traversal handle these nodes to produce the inorder sequence without extra space?

hard

A. It creates temporary right links from the rightmost node of left subtree back to current node

B. It skips nodes with only left children to avoid infinite loops

C. It uses recursion internally to handle left-only nodes

D. It converts the tree into a linked list before traversal

Solution

1. Step 1: Understand Morris Traversal threading

   For nodes with left children, Morris Traversal finds the rightmost node in left subtree and links its right pointer to current node temporarily.

2. Step 2: Explain handling of left-only nodes

   This threading allows traversal to return to current node after left subtree is processed, enabling inorder traversal without stack or recursion.

3. Final Answer:

   It creates temporary right links from the rightmost node of left subtree back to current node -> Option A

4. Quick Check:

   Threading rightmost left subtree node to current [OK]

Hint: Thread rightmost left child back to current node [OK]

Common Mistakes:

• Thinking recursion is used internally
• Assuming nodes are skipped
• Believing tree is converted to linked list