Morris Traversal Inorder Without Stack in DSA Go - Deep Dive

Overview - Morris Traversal Inorder Without Stack

What is it?

Morris Traversal is a way to visit all nodes of a binary tree in order without using extra space like a stack or recursion. It changes the tree temporarily by creating links to predecessors, allowing traversal with only constant extra memory. After visiting, it restores the tree to its original shape. This method is useful when memory is limited or recursion is not allowed.

Why it matters

Without Morris Traversal, inorder tree traversal usually needs extra memory for a stack or recursion, which can be costly for large trees or limited memory environments. Morris Traversal solves this by using the tree's own structure to remember where to go next, saving memory and improving efficiency. This can be critical in embedded systems or performance-sensitive applications.

Where it fits

Before learning Morris Traversal, you should understand binary trees and basic inorder traversal using recursion or a stack. After mastering Morris Traversal, you can explore other space-optimized tree traversals and advanced tree algorithms like threaded binary trees or tree flattening.

Mental Model

Core Idea

Morris Traversal visits nodes by temporarily linking each node's predecessor back to it, enabling inorder traversal without extra memory.

Think of it like...

Imagine walking through a maze where you leave temporary arrows on walls pointing back to where you came from, so you can return without getting lost or carrying a map.

Binary Tree Node Structure:

       ┌───────┐
       │ Node  │
       │  val  │
       │ left  │───┐
       │ right │───┼──> Next Node
       └───────┘   │
                   │
Morris Traversal Steps:

 1. Start at root
 2. If left child is null, visit node and go right
 3. Else find rightmost node in left subtree (predecessor)
 4. If predecessor's right is null, link it to current node and go left
 5. Else remove link, visit current node, go right

Flowchart:

[Start] --> [Current node]
    |
    v
[Left child null?] --Yes--> [Visit node] --> [Go right]
    |
   No
    |
    v
[Find predecessor]
    |
    v
[Predecessor right null?] --Yes--> [Link predecessor right to current] --> [Go left]
    |
   No
    |
    v
[Remove link] --> [Visit node] --> [Go right]

Build-Up - 6 Steps

1

Foundation

Basic Binary Tree Inorder Traversal

Concept: Understanding how inorder traversal visits nodes in left-root-right order using recursion.

Inorder traversal means visiting the left subtree, then the current node, then the right subtree. The simplest way is using recursion: func inorder(node *Node) { if node == nil { return } inorder(node.left) fmt.Print(node.val, " -> ") inorder(node.right) } This prints nodes in sorted order for binary search trees.

Result

For tree 1 <- 2 -> 3, output: 1 -> 2 -> 3 ->

Understanding recursion is key because Morris Traversal mimics this order without using recursion or extra memory.

2

Foundation

Inorder Traversal Using Stack

Concept: Using a stack to simulate recursion and keep track of nodes to visit next.

Instead of recursion, we use a stack to remember nodes: func inorderStack(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.Print(current.val, " -> ") current = current.right } } This uses extra memory proportional to tree height.

Result

For tree 1 <- 2 -> 3, output: 1 -> 2 -> 3 ->

Stacks help us remember where to return after visiting left children, but they use extra memory.

3

Intermediate

Finding Predecessor Node in Binary Tree

Concept: Identifying the rightmost node in the left subtree, called the predecessor, to create temporary links.

For a node with a left child, its inorder predecessor is the rightmost node in its left subtree: func findPredecessor(node *Node) *Node { pred := node.left for pred.right != nil && pred.right != node { pred = pred.right } return pred } This helps us know where to return after visiting left subtree.

Result

For node 2 with left child 1, predecessor is node 1.

Knowing the predecessor lets us create temporary links to return without a stack.

4

Intermediate

Creating Temporary Links for Traversal

🤔Before reading on: do you think modifying the tree structure temporarily can help avoid using extra memory? Commit to yes or no.

Concept: Using the predecessor's right pointer to link back to the current node, enabling traversal without stack or recursion.

When predecessor's right is nil, set it to current node to remember where to return: if pred.right == nil { pred.right = current current = current.left } Later, when we find pred.right points back to current, we remove the link and visit current: else { pred.right = nil fmt.Print(current.val, " -> ") current = current.right } This creates a threaded path for traversal.

Result

Temporary links allow traversal without extra memory, visiting nodes in correct order.

Temporarily changing the tree structure cleverly replaces the need for a stack or recursion.

5

Advanced

Full Morris Inorder Traversal Implementation

🤔Before reading on: do you think Morris Traversal changes the tree permanently or restores it after traversal? Commit to your answer.

Concept: Combining predecessor finding and temporary linking to traverse the tree in order without extra memory and restoring the tree afterwards.

Complete Go code: func morrisInorder(root *Node) { current := root for current != nil { if current.left == nil { fmt.Print(current.val, " -> ") current = current.right } else { pred := current.left for pred.right != nil && pred.right != current { pred = pred.right } if pred.right == nil { pred.right = current current = current.left } else { pred.right = nil fmt.Print(current.val, " -> ") current = current.right } } } } This prints nodes in inorder without stack or recursion.

Result

For tree 1 <- 2 -> 3, output: 1 -> 2 -> 3 ->

Restoring the tree after traversal ensures no side effects, making Morris Traversal safe for production.

6

Expert

Performance and Limitations of Morris Traversal

🤔Before reading on: do you think Morris Traversal is always faster than stack-based traversal? Commit to yes or no.

Concept: Understanding the time complexity trade-offs and when Morris Traversal may be less efficient due to repeated tree modifications.

Morris Traversal runs in O(n) time but may visit some nodes multiple times due to threading and unthreading. It uses O(1) space, unlike stack-based O(h) space. However, modifying pointers can be costly or unsafe in concurrent or immutable trees. Also, it only works on binary trees, not general graphs. In practice, Morris Traversal is best when memory is very limited and tree modification is allowed.

Result

Morris Traversal trades extra visits for constant space, with restored tree structure after traversal.

Knowing the trade-offs helps decide when Morris Traversal is the right tool versus simpler stack-based methods.

Under the Hood

Morris Traversal works by temporarily modifying the tree's right pointers of inorder predecessors to point back to the current node. This creates a threaded binary tree structure during traversal. When the traversal returns to a node via this thread, it removes the temporary link and visits the node. This avoids using a stack or recursion by encoding the return path within the tree itself.

Why designed this way?

Traditional inorder traversal uses recursion or a stack, which requires extra memory proportional to tree height. Morris Traversal was designed to reduce memory usage to constant by cleverly reusing the tree's null right pointers as temporary threads. This design balances memory efficiency with the need to restore the tree to its original form, avoiding permanent structural changes.

Traversal Flow:

[Current Node]
    |
    v
[Left Child?] --No--> [Visit Node] --> [Go Right]
    |
   Yes
    |
    v
[Find Predecessor]
    |
    v
[Predecessor Right Null?] --Yes--> [Set Predecessor Right to Current] --> [Go Left]
    |
   No
    |
    v
[Remove Link] --> [Visit Node] --> [Go Right]

Myth Busters - 3 Common Misconceptions

Quick: Does Morris Traversal permanently change the tree structure? Commit to yes or no.

Common Belief: Morris Traversal permanently modifies the tree, which can corrupt data.

Reality: Morris Traversal only temporarily modifies the tree by creating and removing threads during traversal, restoring the original structure fully.

Why it matters: Believing the tree is permanently changed may prevent using Morris Traversal in safe contexts where it is actually beneficial.

Quick: Is Morris Traversal always faster than recursive traversal? Commit to yes or no.

Common Belief: Morris Traversal is always faster because it uses no extra memory.

Reality: Morris Traversal may visit some nodes multiple times, making it sometimes slower than recursive or stack-based traversal despite using less memory.

Why it matters: Assuming Morris Traversal is always faster can lead to poor performance choices in time-critical applications.

Quick: Can Morris Traversal be used on any tree-like structure? Commit to yes or no.

Common Belief: Morris Traversal works on all tree and graph structures.

Reality: Morris Traversal only works on binary trees because it relies on left and right child pointers and their null states to create threads.

Why it matters: Trying to apply Morris Traversal to non-binary trees or graphs will fail or cause errors.

Expert Zone

1

Morris Traversal's temporary threading can cause subtle bugs if the tree is accessed concurrently during traversal.

2

The algorithm assumes the tree nodes' right pointers can be safely modified; immutable or shared trees require different approaches.

3

Repeated visits to nodes during threading and unthreading can affect cache performance and runtime in large trees.

When NOT to use

Avoid Morris Traversal when tree immutability is required, in concurrent environments without locks, or when simplicity and speed are more important than memory. Use recursive or stack-based inorder traversal instead.

Production Patterns

Morris Traversal is used in embedded systems with tight memory constraints, in interview problems testing space optimization, and in systems where recursion depth is limited. It also inspires threaded binary trees that permanently maintain such links for fast traversal.

Connections

Threaded Binary Trees

Morris Traversal temporarily creates threads similar to permanent threaded binary trees.

Understanding Morris Traversal helps grasp how threaded binary trees maintain traversal paths without stacks.

Recursion and Stack Memory

Morris Traversal replaces recursion and stack memory with tree pointer manipulation.

Knowing Morris Traversal deepens understanding of how recursion can be simulated without extra memory.

Maze Navigation Algorithms

Both use temporary markers or paths to avoid getting lost and to return to previous points.

Recognizing this connection shows how algorithms in different fields solve navigation and memory problems similarly.

Common Pitfalls

#1 Not restoring the tree's right pointers after traversal.

Wrong approach:

func morrisInorder(root *Node) {
current := root
for current != nil {
if current.left == nil {
fmt.Print(current.val, " -> ")
current = current.right
} else {
pred := current.left
for pred.right != nil && pred.right != current {
pred = pred.right
}
if pred.right == nil {
pred.right = current
current = current.left
} else {
// Missing pred.right = nil here
fmt.Print(current.val, " -> ")
current = current.right
}
}
}
}

Correct approach:

func morrisInorder(root *Node) {
current := root
for current != nil {
if current.left == nil {
fmt.Print(current.val, " -> ")
current = current.right
} else {
pred := current.left
for pred.right != nil && pred.right != current {
pred = pred.right
}
if pred.right == nil {
pred.right = current
current = current.left
} else {
pred.right = nil // Restore link
fmt.Print(current.val, " -> ")
current = current.right
}
}
}
}

Root cause:

Forgetting to remove temporary links causes the tree to remain altered, breaking its structure.

#2 Trying to use Morris Traversal on a tree with no left children.

Wrong approach:

func morrisInorder(root *Node) {
current := root
for current != nil {
pred := current.left
// Assumes left child exists without checking
pred = pred.right
// ... rest of code
}
}

Correct approach:

func morrisInorder(root *Node) {
current := root
for current != nil {
if current.left == nil {
fmt.Print(current.val, " -> ")
current = current.right
} else {
pred := current.left
for pred.right != nil && pred.right != current {
pred = pred.right
}
if pred.right == nil {
pred.right = current
current = current.left
} else {
pred.right = nil
fmt.Print(current.val, " -> ")
current = current.right
}
}
}
}

Root cause:

Not handling nil left children leads to runtime errors or incorrect traversal.

Key Takeaways

Morris Traversal enables inorder traversal of binary trees without extra memory by temporarily modifying tree pointers.

It works by creating and removing threads from a node's inorder predecessor back to the node itself.

The tree is fully restored after traversal, ensuring no permanent changes.

This method trades extra visits to nodes for constant space usage, useful in memory-constrained environments.

Understanding Morris Traversal deepens insight into how recursion and stacks can be simulated using data structure manipulation.