Morris Traversal Inorder Without Stack in DSA Go - Execution Trace

Concept Flow - Morris Traversal Inorder Without Stack

Start at root

↓

Check if current.left is nil?

Yes→Visit current node

↓

Move to current.right

↓

Find predecessor in left subtree

↓

Check if predecessor.right is nil?

Yes→Make thread: predecessor.right = current

↓

Remove thread: predecessor.right = nil

↓

Move current to current.left

↓

Move current to current.right

↓

Repeat

This flow shows how Morris Traversal visits nodes without stack by creating temporary threads to predecessors and removing them after visiting.

Execution Sample

DSA Go

func morrisInorder(root *Node) {
  current := root
  for current != nil {
    if current.left == nil {
      visit(current)
      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
        visit(current)
        current = current.right
      }
    }
  }
}

This code performs inorder traversal of a binary tree without using stack or recursion by creating temporary threads.

Execution Table

Step	Operation	Current Node	Predecessor	Thread Created/Removed	Visual State
1	Start at root	1	nil	nil	1 / \ 2 3
2	current.left != nil, find predecessor	1	2	nil	1 / \ 2 3
3	predecessor.right == nil, create thread	1	2	Thread 2.right -> 1	1 / \ 2->1 3
4	Move current to left child	2	nil	nil	1 / \ 2->1 3
5	current.left == nil, visit node	2	nil	nil	Visited: 2 1 / \ 2->1 3
6	Move current to right child (thread)	1	2	nil	1 / \ 2->1 3
7	predecessor.right == current, remove thread	1	2	Remove thread 2.right	1 / \ 2 3
8	Visit current node	1	nil	nil	Visited: 2,1 1 / \ 2 3
9	Move current to right child	3	nil	nil	1 / \ 2 3
10	current.left == nil, visit node	3	nil	nil	Visited: 2,1,3 1 / \ 2 3
11	Move current to right child (nil)	nil	nil	nil	Traversal complete
12	Exit	nil	nil	nil	Traversal ends as current is nil

💡 Traversal ends when current becomes nil, meaning all nodes visited.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 7	After Step 9	Final
current	1	1	2	1	1	3	nil
predecessor	nil	2	nil	2	2	nil	nil
thread	nil	Created at 2.right	Created at 2.right	Created at 2.right	Removed at 2.right	nil	nil
visited nodes	[]	[]	[]	[2]	[2]	[2,1]	[2,1,3]

Key Moments - 3 Insights

Why do we create a thread from predecessor.right to current?

Creating a thread allows us to return to the current node after finishing the left subtree without using a stack, as shown in steps 3 and 6.

Why do we remove the thread after visiting the current node?

Removing the thread restores the original tree structure and prevents infinite loops, as seen in step 7 where the thread is removed before visiting the node.

What happens when current.left is nil?

When current.left is nil, we visit the current node immediately and move to current.right, as in steps 5 and 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 4?

A 3

B 1

C 2

D nil

💡 Hint

Check the 'current' column in execution_table row for step 4.

At which step is the thread from predecessor.right to current removed?

A Step 7

B Step 3

C Step 6

D Step 9

💡 Hint

Look at the 'Thread Created/Removed' column in execution_table.

If the tree had no left children, how would the traversal proceed?

A It would create threads for each node

B It would visit nodes and move right immediately without threads

C It would get stuck in an infinite loop

D It would skip visiting nodes

💡 Hint

Refer to steps where current.left == nil in execution_table and variable_tracker.

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Uses threaded binary tree to avoid stack/recursion
- Creates temporary threads from predecessor.right to current
- Visits nodes when left subtree is done or no left child
- Removes threads to restore tree
- Time: O(n), Space: O(1)

Full Transcript

Morris Traversal is a way to do inorder traversal of a binary tree without using extra space like stack or recursion. It works by creating temporary threads from the rightmost node of the left subtree (predecessor) back to the current node. This thread acts like a return path after visiting the left subtree. When the thread is encountered again, it is removed and the current node is visited. If the current node has no left child, it is visited immediately and traversal moves to the right child. This process continues until all nodes are visited and the current pointer becomes nil, ending the traversal. This method modifies the tree temporarily but restores it before finishing, achieving O(n) time and O(1) space complexity.

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)