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.