Morris Traversal Inorder Without Stack in DSA Go

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 -> 1, 3 and 4 -> 5; perform inorder traversal using Morris method

Goal: Print nodes in inorder: 1 -> 2 -> 3 -> 4 -> 5 without stack or recursion

Step 1: Start at root 4, find predecessor in left subtree (rightmost of 2's subtree)

4 [curr] -> 2 -> 1 -> 3 -> 5
Temporary link not set yet

Why: We need to find where to return after left subtree is done

Step 2: Predecessor is 3, set 3's right pointer to 4 (threading)

3 -> 4 (thread)
4 [curr]
Left subtree traversal begins

Why: Thread allows returning to 4 after finishing left subtree

Step 3: Move curr to left child 2

2 [curr] -> 1 -> 3 -> 4 -> 5

Why: Traverse left subtree first

Step 4: Find predecessor of 2 (rightmost in left subtree), which is 1

1 -> 2 [curr] -> 3 -> 4 -> 5

Why: Prepare threading for node 2

Step 5: Set 1's right pointer to 2 (threading)

1 -> 2 (thread)
2 [curr]

Why: Thread allows returning to 2 after left subtree

Step 6: Move curr to left child 1

1 [curr] -> 2 -> 3 -> 4 -> 5

Why: Go deeper to leftmost node

Step 7: 1 has no left child, print 1 and move to right (which is threaded to 2)

Print 1
Curr moves to 2 via thread

Why: Visit node and return to parent

Step 8: At 2, thread detected from 1, remove thread, print 2, move to right child 3

Print 2
Thread removed
Curr -> 3

Why: Finish left subtree and move right

Step 9: 3 has no left child, print 3, move to right (threaded to 4)

Print 3
Curr -> 4 via thread

Why: Visit node and return to root

Step 10: At 4, thread detected from 3, remove thread, print 4, move to right child 5

Print 4
Thread removed
Curr -> 5

Why: Finish left subtree and move right

Step 11: 5 has no left child, print 5, move to right null

Print 5
Curr -> null

Why: Visit last node and end traversal

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func morrisInorder(root *TreeNode) {
	curr := root
	for curr != nil {
		if curr.Left == nil {
			fmt.Printf("%d -> ", curr.Val) // print current node
			curr = curr.Right // move right
		} else {
			// find inorder predecessor
			pre := curr.Left
			for pre.Right != nil && pre.Right != curr {
				pre = pre.Right // move to rightmost node in left subtree
			}
			if pre.Right == nil {
				pre.Right = curr // create thread
				curr = curr.Left // move left
			} else {
				pre.Right = nil // remove thread
				fmt.Printf("%d -> ", curr.Val) // print current node
				curr = curr.Right // move right
			}
		}
	}
	fmt.Print("null\n")
}

func main() {
	// Construct tree:
	//     4
	//    / \
	//   2   5
	//  / \
	// 1   3
	root := &TreeNode{4, nil, nil}
	root.Left = &TreeNode{2, nil, nil}
	root.Right = &TreeNode{5, nil, nil}
	root.Left.Left = &TreeNode{1, nil, nil}
	root.Left.Right = &TreeNode{3, nil, nil}

	morrisInorder(root)
}

for curr != nil {

loop until all nodes are visited

if curr.Left == nil {

if no left child, visit node and move right

fmt.Printf("%d -> ", curr.Val)

print current node value

curr = curr.Right

move to right child

pre := curr.Left

find inorder predecessor in left subtree

for pre.Right != nil && pre.Right != curr { pre = pre.Right }

move to rightmost node of left subtree or thread back to curr

if pre.Right == nil { pre.Right = curr; curr = curr.Left }

create thread and move left

else { pre.Right = nil; print curr; curr = curr.Right }

remove thread, 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 threading and removal

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

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

Edge Cases

Empty tree (root is nil)

No output, traversal ends immediately

DSA Go

for curr != nil {

Tree with single node

Prints the single node value and ends

DSA Go

if curr.Left == nil {

Tree with no left children (right skewed)

Traversal prints nodes in order by moving right only

DSA Go

if curr.Left == nil {

When to Use This Pattern

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

Common Mistakes

Mistake: Not removing the temporary thread after visiting the predecessor
Fix: Always remove the thread by setting predecessor's right pointer back to nil after visiting current node

Mistake: Moving curr to left child without creating thread
Fix: Create thread from predecessor to current before moving left to ensure return path

Summary

Performs inorder traversal without extra space by temporarily linking nodes to their inorder predecessors.

Use when you want inorder traversal with O(1) space and can modify the tree temporarily.

The key insight is creating and removing temporary threads to remember return paths without stack or recursion.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to the traditional recursive or stack-based methods?

easy

A. It is faster than all other traversal methods

B. It requires the tree to be balanced

C. It only works on binary search trees

D. It uses no extra space for stack or recursion

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal modifies the tree temporarily to avoid using stack or recursion, so it uses O(1) extra space.

2. Step 2: Compare with other methods

   Traditional inorder traversal uses recursion or stack which requires O(h) space, where h is tree height.

3. Final Answer:

   It uses no extra space for stack or recursion -> Option D

4. Quick Check:

   Morris Traversal = O(1) space [OK]

Hint: Morris Traversal saves space by threading nodes [OK]

Common Mistakes:

• Thinking it is faster than all methods
• Assuming it only works on BSTs
• Believing it needs balanced trees

2. Which of the following Go code snippets correctly initializes a pointer to the current node for Morris inorder traversal?

easy

A. current := root

B. var current *Node = nil

C. current := &root

D. current := root.left

Solution

1. Step 1: Understand pointer initialization

   For traversal, current should start at root node, so current := root is correct.

2. Step 2: Check other options

   var current *Node = nil sets current to nil, which stops traversal immediately. current := &root takes address of root pointer, incorrect. current := root.left starts at left child, skipping root.

3. Final Answer:

   current := root -> Option A

4. Quick Check:

   Start traversal at root = current := root [OK]

Hint: Start traversal pointer at root node [OK]

Common Mistakes:

• Initializing current as nil
• Taking address of root pointer
• Starting at root.left instead of root

3. Given the following binary tree and Morris inorder traversal code, what is the printed output?

    2
   / \
  1   3

func morrisInorder(root *Node) {
    current := root
    for current != nil {
        if current.Left == nil {
            fmt.Print(current.Val, " ")
            current = current.Right
        } else {
            pre := current.Left
            for pre.Right != nil && pre.Right != current {
                pre = pre.Right
            }
            if pre.Right == nil {
                pre.Right = current
                current = current.Left
            } else {
                pre.Right = nil
                fmt.Print(current.Val, " ")
                current = current.Right
            }
        }
    }
}

medium

A. 2 1 3

B. 1 2 3

C. 3 2 1

D. 1 3 2

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, root, then right subtree. For tree 2 with left 1 and right 3, order is 1 2 3.

2. Step 2: Trace Morris traversal output

   Morris traversal prints nodes in inorder without stack. The code prints 1, then 2, then 3 with spaces.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Inorder of given tree = 1 2 3 [OK]

Hint: Inorder prints left-root-right sequence [OK]

Common Mistakes:

• Confusing preorder or postorder output
• Misreading the tree structure
• Ignoring Morris threading logic

4. Consider this snippet of Morris inorder traversal in Go. What is the bug that causes an infinite loop?

current := root
for current != nil {
    if current.Left != nil {
        pre := current.Left
        for pre.Right != nil {
            pre = pre.Right
        }
        pre.Right = current
        current = current.Left
    } else {
        fmt.Print(current.Val, " ")
        current = current.Right
    }
}

medium

A. Printing node values before traversal

B. Incorrect initialization of current pointer

C. Missing check if pre.Right == current before setting pre.Right = current

D. Not updating current to current.Left in else block

Solution

1. Step 1: Analyze inner loop for threading

   The inner loop finds rightmost node of left subtree. Without checking if pre.Right == current, it keeps looping infinitely.

2. Step 2: Identify missing condition causing infinite loop

   Correct Morris traversal checks if pre.Right is nil or points to current to avoid infinite loop. Missing this causes infinite loop.

3. Final Answer:

   Missing check if pre.Right == current before setting pre.Right = current -> Option C

4. Quick Check:

   Check pre.Right == current to avoid loops [OK]

Hint: Always check if thread already exists before linking [OK]

Common Mistakes:

• Skipping pre.Right == current check
• Wrong pointer updates
• Printing too early

5. You want to modify Morris inorder traversal to count the number of nodes in a binary tree without using extra space or recursion. Which change correctly achieves this?

hard

A. Add a counter variable and increment it each time you print a node's value during traversal

B. Increment counter only when creating a thread (pre.Right = current)

C. Increment counter only when removing a thread (pre.Right = nil)

D. Increment counter only when current.Left is nil

Solution

1. Step 1: Identify when nodes are visited in Morris traversal

   Nodes are printed exactly once: when current.Left == nil or when removing the thread (pre.Right != nil).

2. Step 2: Choose correct increment point for counting

   Incrementing the counter each time a node's value is printed ensures every node is counted exactly once.

3. Final Answer:

   Add a counter variable and increment it each time you print a node's value during traversal -> Option A

4. Quick Check:

   Increment on every print operation [OK]

Hint: Count nodes when printing each node [OK]

Common Mistakes:

• Incrementing only when current.Left is nil (misses nodes with left subtrees)
• Incrementing when creating threads (counts only non-leaf nodes)
• Incrementing when removing threads (counts only non-leaf nodes)