Morris Traversal Inorder Without Stack in DSA Javascript - 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 us to move back up the tree. After visiting, it restores the tree to its original shape. This method helps us save space 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-sensitive situations. Without it, some systems would struggle with large trees or run out of memory.

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-efficient tree algorithms and advanced tree manipulations like threaded binary trees or tree flattening.

Mental Model

Core Idea

Morris Traversal visits nodes by temporarily linking each 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 remembering the path.

  ┌─────────────┐
  │ Current Node│
  └─────┬───────┘
        │
        ▼
  ┌─────────────┐       Temporary link (thread)
  │Predecessor  │◄─────────────────────────────┐
  └─────────────┘                              │
        │                                      │
        ▼                                      │
  Move to left child                           │
                                               │
  When predecessor's right is null, create link
  When link exists, remove it and visit current

Build-Up - 7 Steps

1

Foundation

Basic Binary Tree Inorder Traversal

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

In a binary tree, inorder traversal means: first visit the left child, then the current node, then the right child. Usually, this is done by calling the function recursively or using a stack to remember nodes.

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: Stack or recursion uses extra memory proportional to tree height.

When traversing a tree with recursion or a stack, each call or push uses memory. For tall trees, this can be large and cause problems like stack overflow or high memory use.

Result

Traversal works but can be inefficient in memory use.

Recognizing memory cost motivates finding traversal methods without extra space.

3

Intermediate

Finding the Predecessor Node

🤔Before reading on: do you think the predecessor of a node is always its left child or can it be deeper? Commit to your answer.

Concept: The predecessor is the rightmost node in the left subtree of the current node.

For a node, its inorder predecessor is found by going to its left child, then moving right as far as possible until no more right child exists. This node comes just before the current node in inorder traversal.

Result

You can find the predecessor without extra memory by following pointers.

Knowing how to find the predecessor is key to creating temporary links for Morris Traversal.

4

Intermediate

Creating and Removing Temporary Links

🤔Before reading on: do you think temporary links should be permanent or removed after use? Commit to your answer.

Concept: Morris Traversal creates a temporary link from predecessor's right to current node, then removes it after visiting.

When the predecessor's right pointer is null, set it to point to the current node. This acts like a thread to return after left subtree is done. When you come back to this link, remove it to restore the tree.

Result

Traversal can move back up without stack or recursion.

Temporarily changing the tree structure allows traversal without extra memory while preserving the original tree.

5

Intermediate

Morris Traversal Algorithm Steps

🤔Before reading on: do you think Morris Traversal visits nodes before or after creating links? Commit to your answer.

Concept: Morris Traversal visits nodes only after left subtree is fully visited, using temporary links to return.

Start at root. While current is not null: - If no left child, visit current and move right. - Else find predecessor. - If predecessor's right is null, link it to current and move current left. - Else remove link, visit current, move right. This visits nodes in inorder without extra memory.

Result

All nodes visited in correct order, tree restored.

Following these steps carefully ensures correct traversal and tree restoration.

6

Advanced

JavaScript Implementation of Morris Traversal

🤔Before reading on: do you think Morris Traversal code is simpler or more complex than recursive traversal? Commit to your answer.

Concept: Implement Morris Traversal in JavaScript using pointer manipulation and loops.

function morrisInorder(root) { let current = root; while (current !== null) { if (current.left === null) { console.log(current.val); 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; console.log(current.val); current = current.right; } } } } // Example tree: // 4 // / \ // 2 5 // / \ // 1 3 // Output: 1 2 3 4 5

Result

Console prints nodes in inorder: 1 2 3 4 5

Seeing the full code helps understand how temporary links and traversal combine in practice.

7

Expert

Handling Edge Cases and Tree Restoration

🤔Before reading on: do you think Morris Traversal can leave the tree changed if interrupted? Commit to your answer.

Concept: Morris Traversal carefully removes all temporary links to restore the tree, but interruptions can leave it altered.

The algorithm removes each temporary link after visiting the node. However, if traversal stops early (e.g., error or break), some links may remain, changing the tree structure. Careful use or cleanup is needed in production.

Result

Tree remains unchanged after full traversal; partial traversal risks modification.

Understanding restoration is crucial for safe use of Morris Traversal in real systems.

Under the Hood

Morris Traversal works by using the tree's null right pointers in the left subtree's rightmost nodes to create temporary threads back to the current node. This allows the traversal to return to a node after visiting its left subtree without using a stack or recursion. The algorithm modifies pointers during traversal but restores them before moving on, preserving the original tree structure.

Why designed this way?

Traditional inorder traversal requires extra memory for recursion or a stack, which can be costly. Morris Traversal was designed to use the tree's existing structure to avoid extra space by temporarily linking nodes. This tradeoff uses pointer manipulation to save memory at the cost of modifying the tree during traversal, which is restored later.

Start
  │
  ▼
[Current Node]
  │
  ├─ If left child is null -> Visit node -> Move right
  │
  └─ Else find predecessor (rightmost in left subtree)
       │
       ├─ If predecessor.right is null -> Set predecessor.right = current (thread) -> Move current left
       │
       └─ Else (thread exists) -> Remove thread -> Visit current -> Move right
  │
  ▼
Repeat until current is null

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 links.

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

Why it matters: Believing the tree is permanently changed may prevent using Morris Traversal where it is safe and beneficial.

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 can be slower due to extra pointer manipulations despite saving memory.

Why it matters: Expecting speed gains alone may lead to wrong choices; Morris Traversal trades time for space.

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

Common Belief: Morris Traversal works on all binary trees without restrictions.

Reality: Morris Traversal requires the ability to modify pointers temporarily; it may not be suitable for immutable or shared trees.

Why it matters: Using Morris Traversal on immutable trees can cause errors or is impossible.

Quick: Does Morris Traversal require a stack or recursion? Commit to yes or no.

Common Belief: Morris Traversal still needs a stack or recursion internally.

Reality: Morris Traversal uses no stack or recursion, relying solely on pointer manipulation.

Why it matters: Misunderstanding this misses the main advantage of Morris Traversal.

Expert Zone

1

Morris Traversal's pointer changes can cause subtle bugs if the tree is accessed concurrently during traversal.

2

The algorithm's efficiency depends on the tree shape; skewed trees may cause more pointer changes.

3

Restoring the tree requires careful removal of threads; missing one can corrupt the tree.

When NOT to use

Avoid Morris Traversal when working with immutable trees, concurrent environments without locks, or when pointer modification is forbidden. Use recursive or stack-based traversal in these cases.

Production Patterns

Morris Traversal is used in memory-constrained embedded systems or interview problems to demonstrate space optimization. It is less common in production due to complexity and potential side effects but valuable for understanding tree pointer manipulation.

Connections

Threaded Binary Trees

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

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

Inorder Tree Traversal

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

Knowing Morris Traversal deepens understanding of inorder traversal mechanics and memory tradeoffs.

Maze Navigation

Both involve leaving temporary markers to find the way back without remembering the full path.

This cross-domain link shows how temporary markers solve navigation problems in different fields.

Common Pitfalls

#1 Leaving temporary links in the tree after traversal.

Wrong approach:

function morrisInorder(root) {
let current = root;
while (current !== null) {
if (current.left === null) {
console.log(current.val);
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 {
// Missing removal of link here
console.log(current.val);
current = current.right;
}
}
}
}

Correct approach:

function morrisInorder(root) {
let current = root;
while (current !== null) {
if (current.left === null) {
console.log(current.val);
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; // Remove temporary link
console.log(current.val);
current = current.right;
}
}
}
}

Root cause:

Forgetting to remove the temporary link causes the tree to remain altered, breaking its structure.

#2 Trying to use Morris Traversal on an immutable tree structure.

Wrong approach:

// Immutable tree nodes with no pointer modification allowed
// Attempting Morris Traversal will fail or cause errors.

Correct approach:

// Use recursive or stack-based inorder traversal for immutable trees.

Root cause:

Morris Traversal requires modifying pointers temporarily, which immutable trees disallow.

#3 Confusing predecessor with parent node during traversal.

Wrong approach:

function findPredecessor(node) {
return node.parent; // Incorrect: predecessor is not always parent
}

Correct approach:

function findPredecessor(node) {
let pred = node.left;
while (pred.right !== null && pred.right !== node) {
pred = pred.right;
}
return pred;
}

Root cause:

Misunderstanding the definition of predecessor leads to wrong pointer manipulations.

Key Takeaways

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

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

This method saves memory but can be more complex and sometimes slower than recursive or stack-based traversal.

Understanding predecessor nodes and pointer manipulation is essential to implement Morris Traversal correctly.

Morris Traversal is best used when memory is limited and pointer modification is allowed.

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 requires a queue to store nodes

D. It uses no extra space like 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 stack or recursion which requires O(h) space, where h is tree height.

3. Final Answer:

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

4. Quick Check:

   Morris Traversal = O(1) space [OK]

Hint: Morris Traversal avoids stack and recursion for space savings [OK]

Common Mistakes:

• Thinking Morris Traversal is faster in time complexity
• Assuming it only works on binary search trees
• Believing it uses extra data structures like queues

2. Which of the following is the correct way to find the inorder predecessor of a node curr in Morris Traversal?

easy

A. Move to the left child of curr and then keep moving right until right child is null or curr

B. Move to the right child of curr until null

C. Move to the left child of curr only once

D. Move to the right child of curr and then keep moving left until left child is null

Solution

1. Step 1: Identify inorder predecessor in Morris Traversal

   The inorder predecessor is the rightmost node in the left subtree of curr.

2. Step 2: Traverse left subtree then rightmost path

   Start at curr.left, move right repeatedly until right child is null or points back to curr.

3. Final Answer:

   Move to the left child of curr and then keep moving right until right child is null or curr -> Option A

4. Quick Check:

   Inorder predecessor = left subtree's rightmost node [OK]

Hint: Inorder predecessor = left child then rightmost path [OK]

Common Mistakes:

• Moving right child first instead of left
• Stopping after one left move without going right
• Confusing predecessor with successor

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

    2
   / \
  1   3

Assuming the traversal prints node values in order.

medium

A. [1, 3, 2]

B. [2, 1, 3]

C. [1, 2, 3]

D. [3, 2, 1]

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then current node, then right subtree.

2. Step 2: Apply Morris traversal on given tree

   Left child is 1, root is 2, right child is 3, so output is [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

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

Hint: Inorder prints left, root, right nodes [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Mixing node visit order
• Assuming traversal prints in reverse

4. Consider this snippet of Morris Traversal code:

while (curr !== null) {
  if (curr.left === null) {
    console.log(curr.val);
    curr = curr.right;
  } else {
    let pred = curr.left;
    while (pred.right !== null && pred.right !== curr) {
      pred = pred.right;
    }
    if (pred.right === null) {
      pred.right = curr;
      curr = curr.left;
    } else {
      pred.right = null;
      console.log(curr.val);
      curr = curr.right;
    }
  }
}

What is the error in this code?

medium

A. It misses printing the current node after restoring links

B. It never prints the current node's value

C. It creates infinite loop by not updating curr

D. It incorrectly sets pred.right to curr.left

Solution

1. Step 1: Check when node values are printed

   Values are printed only when curr.left === null, but after restoring links, printing is missing.

2. Step 2: Identify missing print after restoring links

   After setting pred.right = null, the code moves curr = curr.right without printing curr.val.

3. Final Answer:

   It misses printing the current node after restoring links -> Option A

4. Quick Check:

   Print missing after restoring links = bug [OK]

Hint: Print node after restoring links to avoid missing values [OK]

Common Mistakes:

• Not printing node after restoring predecessor link
• Confusing when to update curr pointer
• Incorrectly modifying tree structure

5. You want to modify Morris Traversal inorder to collect node values in an array instead of printing. Which change is necessary to correctly collect all nodes in order?

hard

A. Push curr.val only when curr.left === null

B. Push curr.val both when curr.left === null and after restoring links

C. Push curr.val only after restoring links

D. Push curr.val before moving to left child

Solution

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

   Nodes are visited either when curr.left === null or after restoring the threaded link.

2. Step 2: Collect values at both visit points

   To collect all nodes in inorder, push curr.val both when curr.left === null and after restoring links (before moving right).

3. Final Answer:

   Push curr.val both when curr.left === null and after restoring links -> Option B

4. Quick Check:

   Collect values at both visits = correct inorder [OK]

Hint: Collect node values at both visits for full inorder [OK]

Common Mistakes:

• Collecting values only once misses nodes
• Collecting before moving left causes wrong order
• Ignoring second visit after restoring links