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.