Morris Traversal Inorder Without Stack in DSA Typescript - 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 big trees or limited memory devices. Morris Traversal solves this by using the tree itself to keep track of progress, making it efficient and memory-friendly. This is important in systems where saving memory is critical, like embedded devices or large data processing.

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 a node's predecessor back to it, allowing traversal without extra memory.

Think of it like...

Imagine walking through a maze where you leave a temporary string tied behind you at each turn to find your way back without carrying a map or notes.

Binary Tree Node Structure:

      ┌───────┐
      │ Node  │
      ├───────┤
      │ left  │───┐
      │ value │   │
      │ right │───┴──▶
      └───────┘

Traversal Steps:

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

This creates temporary 'threads' to remember where to return.

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, and right child 3, the inorder sequence is 1, 2, 3. Usually, this is done using recursion or a stack to remember nodes.

Result

Visiting nodes 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 Recursion and Stack in Traversal

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

Recursion uses the call stack to remember nodes, and iterative methods use an explicit stack. Both require extra space, which can be large for deep trees. This can cause memory issues or slowdowns in constrained environments.

Result

Extra memory usage grows with tree height, e.g., O(h) where h is tree height.

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

3

Intermediate

Finding the Inorder Predecessor in a Tree

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

For a given node, its inorder predecessor is the rightmost node in its left subtree. This node comes just before the current node in inorder traversal. Finding it helps create temporary links to return after visiting left subtree.

Result

For node 2 with left child 1, predecessor is node 1; for node 5 with left subtree, predecessor is rightmost node there.

Identifying the predecessor is key to creating temporary threads that replace stacks.

4

Intermediate

Creating Temporary Threads to Remember Path

🤔Before reading on: do you think we can traverse a tree without extra memory by changing the tree temporarily? Commit to yes or no.

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

Instead of using a stack, we temporarily change the tree by making the predecessor's right pointer point to the current node. This acts like a thread or marker to return after finishing the left subtree. After visiting, we remove this link to restore the tree.

Result

Tree temporarily changes but is restored after traversal; no extra stack needed.

Using the tree itself to store traversal state avoids extra memory and keeps the tree intact.

5

Intermediate

Morris Traversal Algorithm Step-by-Step

🤔Before reading on: do you think Morris Traversal can handle all binary trees without breaking? Commit to yes or no.

Concept: Learn the full Morris Traversal process combining predecessor finding and threading.

Algorithm: 1. Initialize current as root. 2. While current is not null: a. If current has no left child, visit current and move right. b. Else, find predecessor in left subtree. i. If predecessor's right is null, set it to current and move current left. ii. Else, reset predecessor's right to null, visit current, move current right. This visits nodes in inorder without stack or recursion.

Result

Nodes visited in inorder: e.g., 1 -> 2 -> 3 -> null for simple tree.

Combining threading and predecessor logic enables efficient, memory-saving traversal.

6

Advanced

Implementing Morris Traversal in TypeScript

🤔Before reading on: do you think the code will modify the tree permanently? Commit to yes or no.

Concept: Translate the Morris Traversal logic into runnable TypeScript code that restores the tree after traversal.

class TreeNode { value: number; left: TreeNode | null; right: TreeNode | null; constructor(value: number) { this.value = value; this.left = null; this.right = null; } } function morrisInorder(root: TreeNode | null): number[] { const result: number[] = []; let current = root; while (current !== null) { if (current.left === null) { result.push(current.value); current = current.right; } else { let 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; result.push(current.value); current = current.right; } } } return result; } // Example usage: // Tree: 2 // / \ // 1 3 // Output: [1, 2, 3]

Result

[1, 2, 3]

Implementing Morris Traversal shows how temporary links enable traversal without extra memory and restore the tree.

7

Expert

Handling Edge Cases and Tree Restoration

🤔Before reading on: do you think Morris Traversal can fail if the tree has cycles or is not a proper binary tree? Commit to yes or no.

Concept: Understand how Morris Traversal handles trees with nulls, single nodes, and ensures the tree is restored exactly.

Morris Traversal assumes a proper binary tree without cycles. It carefully creates and removes temporary links to avoid permanent changes. If the tree has cycles or is malformed, traversal may loop infinitely or corrupt data. The algorithm visits each node at most twice, ensuring O(n) time and O(1) space. After traversal, all temporary links are removed, restoring the original tree structure.

Result

Traversal completes correctly, tree structure unchanged after traversal.

Knowing the assumptions and restoration process prevents bugs and misuse in complex or corrupted trees.

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 link that acts like a bookmark to return after visiting the left subtree. The traversal moves left until it hits a node with no left child, visits it, then follows the thread back to the parent. After visiting, it removes the thread to restore the tree. This avoids using extra memory for stacks or recursion by reusing the tree's pointers.

Why designed this way?

Traditional inorder traversal uses extra memory to remember nodes, which can be costly. Morris Traversal was designed to optimize space by using the tree itself to store traversal state temporarily. This design trades a small amount of pointer manipulation for significant memory savings. Alternatives like threaded binary trees permanently add such links, but Morris Traversal creates and removes them on the fly, preserving the original tree.

Traversal Flow:

Start at root
   │
   ▼
Check left child?
 ┌───────────────┐
 │               │
Yes             No
 │               │
Find predecessor  Visit node
 │               │
Is predecessor's right null?
 ┌───────────────┐
 │               │
Yes             No
 │               │
Set thread      Remove thread
Move left       Visit node
                Move right

Repeat until current is null

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 changing pointers.

Reality: Morris Traversal only temporarily changes pointers and restores the tree to its original form after traversal.

Why it matters: Believing the tree is permanently changed may prevent using Morris Traversal in applications where tree integrity is critical.

Quick: Can Morris Traversal be used on any graph structure? Commit to yes or no.

Common Belief: Morris Traversal works on any graph, not just binary trees.

Reality: Morris Traversal only works on proper binary trees without cycles; it relies on tree properties to create and remove threads safely.

Why it matters: Using Morris Traversal on graphs or malformed trees can cause infinite loops or data corruption.

Quick: Does Morris Traversal always visit nodes exactly once? Commit to yes or no.

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

Reality: Nodes may be visited twice: once when creating the thread and once when removing it and visiting the node.

Why it matters: Assuming single visit can lead to incorrect reasoning about traversal time or side effects during visits.

Expert Zone

1

Morris Traversal visits some nodes twice but still achieves O(n) time because each edge is traversed at most twice.

2

The temporary threads are created only on the rightmost nodes of left subtrees, minimizing pointer changes.

3

Restoring the tree after traversal is crucial; forgetting to remove threads leads to corrupted trees and bugs.

When NOT to use

Avoid Morris Traversal when the tree structure must remain untouched during traversal, such as in concurrent environments or when nodes have additional metadata that must not be altered. Use iterative traversal with explicit stacks or recursion instead.

Production Patterns

Morris Traversal is used in memory-constrained systems like embedded devices or when processing large trees where stack overflow is a risk. It is also used in interview problems to demonstrate space optimization and in systems where temporary pointer manipulation is safe and reversible.

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 store traversal paths to optimize inorder traversal.

Call Stack in Recursion

Morris Traversal replaces the call stack with temporary tree links to remember traversal state.

Knowing how recursion uses the call stack clarifies why Morris Traversal's pointer manipulation can save memory.

Maze Navigation

Both involve leaving temporary markers to find the way back without external memory.

Recognizing this pattern in different fields shows how temporary state storage can solve navigation problems efficiently.

Common Pitfalls

#1 Forgetting to remove the temporary thread after visiting the node.

Wrong approach:

if (predecessor.right === null) {
predecessor.right = current;
current = current.left;
} else {
// Missing: predecessor.right = null;
result.push(current.value);
current = current.right;
}

Correct approach:

if (predecessor.right === null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null; // Remove thread
result.push(current.value);
current = current.right;
}

Root cause:

Not restoring the tree pointer causes permanent modification and potential infinite loops.

#2 Trying Morris Traversal on a tree with cycles or malformed pointers.

Wrong approach:

// Using Morris Traversal on a graph or cyclic structure leads to infinite loop
while (current !== null) {
// traversal logic
}

Correct approach:

// Ensure input is a proper binary tree without cycles before Morris Traversal
function isValidBinaryTree(root) {
// validation logic
}
if (isValidBinaryTree(root)) {
morrisInorder(root);
}

Root cause:

Morris Traversal assumes a proper binary tree; cycles break traversal logic.

Key Takeaways

Morris Traversal enables inorder traversal without extra memory by temporarily linking nodes to their predecessors.

It modifies the tree during traversal but always restores it, preserving the original structure.

This method is efficient in memory use and useful in environments with limited resources.

Understanding predecessor nodes and temporary threading is key to mastering Morris Traversal.

Careful handling of edge cases and restoration prevents bugs and ensures correct traversal.