Morris Traversal Inorder Without Stack in DSA Typescript

Mental Model

We visit nodes in order without using extra memory by temporarily changing tree links to remember where to return.

Analogy: Imagine walking through a maze and leaving temporary signs on walls to find your way back without carrying a map or writing notes.

    4
   / \
  2   5
 / \
1   3

No extra stack or recursion, just clever link changes.

Dry Run Walkthrough

Input: Binary tree: 4 -> 2, 5, 1, 3 (root 4 with left child 2 and right child 5; 2 has children 1 and 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 (rightmost of 2's subtree)

4 [curr] -> 2 -> 5 -> 1 -> 3
Predecessor of 4 is 3

Why: We need to find where to return after visiting left subtree

Step 2: Make 3's right point to 4 (thread), move curr to 2

4 -> 2 [curr] -> 5 -> 1 -> 3 -> 4 (thread)
Thread created to remember return

Why: Thread lets us come back to 4 after left subtree

Step 3: At 2, find predecessor (rightmost of 1's subtree), which is 1

4 -> 2 [curr] -> 5 -> 1 -> 3 -> 4 (thread)
Predecessor of 2 is 1

Why: Find return point after left subtree of 2

Step 4: Make 1's right point to 2 (thread), move curr to 1

4 -> 2 -> 5 -> 1 [curr] -> 3 -> 4 (thread)
1's right points to 2

Why: Thread remembers to return to 2 after 1

Step 5: At 1, no left child, print 1, move curr to right (which is thread to 2)

Printed: 1
4 -> 2 -> 5 -> 1 -> 3 -> 4
Curr moves to 2 via thread

Why: No left subtree, so print and return

Step 6: At 2, thread found from 1, remove thread, print 2, move curr to right 3

Printed: 1 -> 2
4 -> 2 -> 5 -> 1 -> 3 -> 4
Thread removed, curr at 3

Why: Left subtree done, print node and go right

Step 7: At 3, no left child, print 3, move curr to right (thread to 4)

Printed: 1 -> 2 -> 3
4 -> 2 -> 5 -> 1 -> 3 -> 4
Curr moves to 4 via thread

Why: No left subtree, print and return

Step 8: At 4, thread found from 3, remove thread, print 4, move curr to right 5

Printed: 1 -> 2 -> 3 -> 4
4 -> 2 -> 5 -> 1 -> 3 -> 4
Thread removed, curr at 5

Why: Left subtree done, print node and go right

Step 9: At 5, no left child, print 5, move curr to right null

Printed: 1 -> 2 -> 3 -> 4 -> 5
5 -> null
Traversal ends

Why: No left subtree, print and finish

Result:

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

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function morrisInorder(root: TreeNode | null): void {
  let curr = root;
  while (curr !== null) {
    if (curr.left === null) {
      console.log(curr.val);
      curr = curr.right; // move to right child
    } else {
      let pred = curr.left;
      while (pred.right !== null && pred.right !== curr) {
        pred = pred.right; // find rightmost node in left subtree
      }
      if (pred.right === null) {
        pred.right = curr; // create thread to curr
        curr = curr.left; // move to left child
      } else {
        pred.right = null; // remove thread
        console.log(curr.val); // print curr
        curr = curr.right; // move to right child
      }
    }
  }
}

// Driver code
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);

morrisInorder(root);

while (curr !== null) {

continue traversal until all nodes visited

if (curr.left === null) {

if no left child, print and move right

curr = curr.right; // move to right child

advance curr to right subtree

let pred = curr.left;

find predecessor in left subtree

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

find rightmost node in left subtree or existing thread

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

create thread and move left

else { pred.right = null; console.log(curr.val); curr = curr.right; }

thread exists: remove it, print node, move right

Output

1

2

3

4

5

Complexity Analysis

Time: O(n) because each edge is visited at most twice during threading and removal

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

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

Edge Cases

Empty tree (root is null)

No output, traversal ends immediately

DSA Typescript

while (curr !== null) {

Tree with single node

Prints the single node value directly

DSA Typescript

if (curr.left === null) {

Tree with no left children (all right skewed)

Prints nodes in order by moving right without threading

DSA Typescript

if (curr.left === null) {

When to Use This Pattern

When asked to do inorder traversal without recursion or stack, think of Morris traversal because it uses tree threading to achieve O(1) space.

Common Mistakes

Mistake: Not removing the thread after visiting left subtree, causing infinite loops
Fix: Ensure to set predecessor.right = null after printing current node

Mistake: Not checking if predecessor.right already points to current node before creating thread
Fix: Check if pred.right === null before creating thread, else remove thread

Summary

Prints inorder traversal of a binary tree without using stack or recursion by temporarily modifying tree links.

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

The key insight is to create and remove temporary threads to remember return points in the tree.