Morris Traversal Inorder Without Stack in DSA Javascript

Mental Model

We visit nodes in order without using extra memory by temporarily linking nodes to their inorder predecessor.

Analogy: Imagine walking through a garden where you tie a ribbon from each tree back to the previous one you visited, so you can return without getting lost or carrying a map.

    4
   / \
  2   5
 / \
1   3

No extra stack or recursion, just temporary links ->

Dry Run Walkthrough

Input: Binary tree: 4 / \ 2 5 / \ 1 3

Goal: Print nodes in inorder: 1 -> 2 -> 3 -> 4 -> 5 without using stack or recursion

Step 1: Start at root (4), find predecessor in left subtree (3), link 3's right to 4

4 ↑
 / \
2   5
/ \
1   3 -> [right->4]

Why: Create temporary link to return to 4 after left subtree

Step 2: Move to left child (2), find predecessor (1), link 1's right to 2

4 ->
2 ↑   5
/ \
1 -> [right->2] 3 -> [right->4]

Why: Create temporary link to return to 2 after left subtree

Step 3: Move to left child (1), no left child, print 1, move to right (which points to 2)

1 ↑ -> [right->2]
2 -> 5
3 -> [right->4]

Why: Leftmost node reached, print and follow temporary link

Step 4: At 2, remove temporary link from 1's right, print 2, move to right child (3)

2 ↑ 5
3 -> [right->4]
1 (link removed)

Why: Left subtree done, restore tree and print current node

Step 5: At 3, no left child, print 3, move to right (which points to 4)

3 ↑ -> [right->4]
4 -> 5
2,1 restored

Why: Print node and follow temporary link back to 4

Step 6: At 4, remove temporary link from 3's right, print 4, move to right child (5)

4 ↑ 5
3 (link removed)
2,1 restored

Why: Left subtree done, restore tree and print current node

Step 7: At 5, no left child, print 5, move to right (null), traversal ends

5 ↑ null
4,3,2,1 restored

Why: Rightmost node reached, traversal complete

Result:

1 -> 2 -> 3 -> 4 -> 5 -> null

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function morrisInorder(root) {
  let curr = root;
  let result = [];
  while (curr !== null) {
    if (curr.left === null) {
      result.push(curr.val); // print current node
      curr = curr.right; // move right
    } else {
      // find inorder predecessor
      let pred = curr.left;
      while (pred.right !== null && pred.right !== curr) {
        pred = pred.right; // move to rightmost node in left subtree
      }
      if (pred.right === null) {
        pred.right = curr; // create temporary link
        curr = curr.left; // move left
      } else {
        pred.right = null; // remove temporary link
        result.push(curr.val); // print current node
        curr = curr.right; // move right
      }
    }
  }
  console.log(result.join(' -> ') + ' -> null');
}

// Driver code
const root = new TreeNode(4,
  new TreeNode(2,
    new TreeNode(1),
    new TreeNode(3)
  ),
  new TreeNode(5)
);
morrisInorder(root);

while (curr !== null) {

continue traversal until all nodes visited

if (curr.left === null) {

if no left child, print and move right

result.push(curr.val);

visit current node

curr = curr.right;

move to right child

let pred = curr.left;

find inorder predecessor in left subtree

while (pred.right !== null && pred.right !== curr) { pred = pred.right; }

move to rightmost node in left subtree or find temporary link

if (pred.right === null) { pred.right = curr; curr = curr.left; }

create temporary link and move left

else { pred.right = null; result.push(curr.val); curr = curr.right; }

remove temporary link, visit node, move right

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because each edge is visited at most twice during traversal

Space: O(1) because no extra stack or recursion is used, only pointers

vs Alternative: Compared to recursive or stack-based inorder traversal which uses O(h) space, Morris traversal uses constant space by temporarily modifying tree links

Edge Cases

Empty tree (root is null)

No output, traversal ends immediately

DSA Javascript

while (curr !== null) {

Tree with single node

Prints the single node value and ends

DSA Javascript

if (curr.left === null) {

Tree with no left children (right skewed)

Traversal prints nodes in order by moving right each time

DSA Javascript

if (curr.left === null) {

When to Use This Pattern

When asked to do inorder traversal without recursion or stack, use Morris Traversal because it cleverly uses tree links to save space.

Common Mistakes

Mistake: Not restoring the tree by removing temporary links, causing infinite loops
Fix: Always remove the temporary link after visiting the node (pred.right = null)

Mistake: Incorrectly finding the inorder predecessor, missing the rightmost node in left subtree
Fix: Traverse right children of left subtree until right is null or points back to current node

Summary

Prints inorder traversal of a binary tree without using stack or recursion by temporarily linking nodes.

Use when you want inorder traversal with O(1) extra space.

The key is to create and remove temporary links to inorder predecessors to remember where to return.

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