Why Morris Traversal Inorder Without Stack in DSA Typescript?

The Big Idea

Discover how to walk through a tree without carrying any extra memory and never get lost!

The Scenario

Imagine you want to walk through a big garden and look at every flower in order. You try to remember every path you took so you don't get lost or miss any flower. But you have no notebook or map, so you keep getting confused and lost.

The Problem

Trying to remember all the paths manually is hard and tiring. You might forget where you came from or miss some flowers. Using a notebook (stack) helps, but carrying it around is bulky and slows you down.

The Solution

Morris Traversal is like cleverly tying small ribbons on branches as you walk, so you can find your way back without carrying a notebook. It lets you visit every flower in order without extra memory, making your walk smooth and easy.

Before vs After

✗ Before

function inorderTraversal(root) {
  const stack = [];
  let current = root;
  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    console.log(current.val);
    current = current.right;
  }
}

✓ After

function morrisInorderTraversal(root) {
  let current = root;
  while (current) {
    if (!current.left) {
      console.log(current.val);
      current = current.right;
    } else {
      let predecessor = current.left;
      while (predecessor.right && predecessor.right !== current) {
        predecessor = predecessor.right;
      }
      if (!predecessor.right) {
        predecessor.right = current;
        current = current.left;
      } else {
        predecessor.right = null;
        console.log(current.val);
        current = current.right;
      }
    }
  }
}

What It Enables

This method enables you to traverse a tree in order using only the tree itself, without extra memory, making your program faster and lighter.

Real Life Example

When a robot explores a maze and must remember paths without carrying extra tools, it can use this trick to mark and revisit places efficiently.

Key Takeaways

Morris Traversal visits nodes in order without extra memory.

It temporarily changes tree links to remember paths.

It is faster and uses less space than stack-based methods.