Why Morris Traversal Inorder Without Stack in DSA Go?

The Big Idea

Discover how to explore a tree without carrying extra memory--like finding your way in a maze using only the doors themselves!

The Scenario

Imagine you want to visit every room in a big house, but you only have one key and no map. You try to remember every door you opened so you can go back, but it's easy to forget and get lost.

The Problem

Using a manual method like writing down every door or carrying a stack of keys slows you down and can cause mistakes. You might lose track or run out of space to keep notes, making the whole process tiring and confusing.

The Solution

Morris Traversal lets you visit every room (node) without extra memory like a stack or recursion. It cleverly uses the house's own doors (tree links) to remember where to go next, so you never get lost and don't need extra tools.

Before vs After

✗ Before

func inorderTraversal(root *Node) {
    stack := []*Node{}
    current := root
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        fmt.Println(current.Value)
        current = current.Right
    }
}

✓ After

func morrisInorderTraversal(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Println(current.Value)
            current = current.Right
        } else {
            predecessor := current.Left
            for predecessor.Right != nil && predecessor.Right != current {
                predecessor = predecessor.Right
            }
            if predecessor.Right == nil {
                predecessor.Right = current
                current = current.Left
            } else {
                predecessor.Right = nil
                fmt.Println(current.Value)
                current = current.Right
            }
        }
    }
}

What It Enables

This method enables efficient tree traversal using no extra memory, making it perfect for large trees or memory-limited environments.

Real Life Example

When a robot explores a maze with limited memory, Morris Traversal helps it remember paths by temporarily marking doors, so it can explore fully without carrying a map or notes.

Key Takeaways

Morris Traversal visits nodes without extra memory like stacks or recursion.

It temporarily changes tree links to remember paths, then restores them.

This makes inorder traversal faster and more memory-efficient.