Morris Traversal Inorder Without Stack in DSA Python - Execution Trace

Concept Flow - Morris Traversal Inorder Without Stack

Start at root

↓

Check if current.left is None?

Yes→Visit current node

↓

Move to current.right

↓

Find predecessor in left subtree

↓

Check if predecessor.right is None?

Yes→Make thread: predecessor.right = current

↓

Remove thread: predecessor.right = None

↓

Move current to current.left

Traverse the tree without stack by creating temporary threads to predecessors, visiting nodes in inorder.

Execution Sample

DSA Python

def morris_inorder(root):
    current = root
    while current:
        if current.left is None:
            print(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                print(current.val)
                current = current.right

Perform inorder traversal without stack by temporarily modifying tree pointers.

Execution Table

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

💡 current becomes None, traversal ends

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	None
predecessor	None	2	None	2	2	None	None
thread	None	Created at 2.right	None	None	Removed at 2.right	None	None
visited_nodes	[]	[]	[2]	[2]	[2,1]	[2,1]	[2,1,3]

Key Moments - 3 Insights

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

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

What happens when predecessor.right is already pointing to current?

It means we finished the left subtree, so we remove the thread and visit the current node, as in step 7 and 8.

Why do we visit the node only when current.left is None or after removing the thread?

Visiting at these points ensures inorder order: left subtree first, then node, then right subtree, as seen in steps 5, 8, and 10.

Visual Quiz - 3 Questions

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

A 2

B 1

C 3

D None

💡 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 3

B Step 7

C Step 5

D Step 10

💡 Hint

Look for 'Remove thread' in the 'Thread Created/Removed' column.

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

A Threads would still be created for all nodes

B Traversal would not visit any nodes

C No threads would be created, nodes visited directly

D Traversal would get stuck in an infinite loop

💡 Hint

Refer to the condition 'current.left is None' in the code and execution_table steps 5 and 10.

Concept Snapshot

Morris Inorder Traversal:
- Traverse without stack or recursion
- Create temporary threads from predecessor.right to current
- Visit node when left is None or after removing thread
- Restore tree structure by removing threads
- Time: O(n), Space: O(1)

Full Transcript

Morris Traversal Inorder Without Stack visits nodes in inorder without extra memory by creating temporary threads from a node's inorder predecessor back to the node. Starting at the root, if the current node has no left child, it is visited and traversal moves to the right child. If there is a left child, the algorithm finds the rightmost node in the left subtree (predecessor). If the predecessor's right pointer is None, a thread is created to the current node and traversal moves left. If the thread already exists, it is removed, the current node is visited, and traversal moves right. This process continues until all nodes are visited and the tree is restored to its original shape.

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 uses no extra space for stack or recursion.

B. It is faster than all other traversal methods.

C. It only works on binary search trees.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal uses threaded binary trees to avoid recursion or stack, 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 A

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris uses threads, no stack or recursion needed [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Believing it only works on BSTs
• Assuming it permanently changes the tree

2. Which of the following code snippets correctly initializes the current node for Morris inorder traversal in Python?

easy

A. current = root

B. current = None

C. current = root.left

D. current = root.right

Solution

1. Step 1: Identify starting point for traversal

   Morris traversal starts from the root node to cover the entire tree.

2. Step 2: Check initialization options

   Setting current = root ensures traversal begins at the tree's root.

3. Final Answer:

   current = root -> Option A

4. Quick Check:

   Start at root node [OK]

Hint: Always start traversal from root node [OK]

Common Mistakes:

• Starting from None causes no traversal
• Starting from root.left misses root node
• Starting from root.right misses left subtree

3. What will be the output of the Morris inorder traversal on the following binary tree?

    2
   / \
  1   3

Assuming the traversal prints node values in order.

medium

A. [2, 1, 3]

B. [1, 3, 2]

C. [3, 2, 1]

D. [1, 2, 3]

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, root, then right subtree.

2. Step 2: Apply Morris traversal order

   For the tree, left is 1, root is 2, right is 3, so output is [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Inorder = left-root-right = [1, 2, 3] [OK]

Hint: Inorder = left, root, right always [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Misreading tree structure
• Assuming traversal prints in insertion order

4. Consider this snippet of Morris inorder traversal code in Python:

current = root
while current:
    if current.left is None:
        print(current.val)
        current = current.right
    else:
        pre = current.left
        while pre.right and pre.right != current:
            pre = pre.right
        if pre.right is None:
            pre.right = current
            current = current.left
        else:
            pre.right = None
            print(current.val)
            current = current.right

What is the main bug if the line pre.right = None is missing?

medium

A. The traversal will print nodes in preorder instead of inorder.

B. The traversal will skip the root node.

C. The traversal will enter an infinite loop.

D. The traversal will cause a syntax error.

Solution

1. Step 1: Understand role of pre.right = None

   This line removes the temporary thread created to return to the root after left subtree traversal.

2. Step 2: Consequence of missing this line

   If not removed, the thread remains, causing the loop to revisit nodes endlessly, creating an infinite loop.

3. Final Answer:

   The traversal will enter an infinite loop. -> Option C

4. Quick Check:

   Missing thread removal = infinite loop [OK]

Hint: Always remove temporary threads to avoid loops [OK]

Common Mistakes:

• Thinking it causes syntax error
• Assuming it changes traversal order
• Believing it skips nodes

5. You want to modify Morris inorder traversal to collect node values in a list instead of printing them. Which of the following code changes correctly achieves this without changing the traversal logic?

result = []
current = root
while current:
    if current.left is None:
        # Change here
        current = current.right
    else:
        pre = current.left
        while pre.right and pre.right != current:
            pre = pre.right
        if pre.right is None:
            pre.right = current
            current = current.left
        else:
            pre.right = None
            # Change here
            current = current.right

hard

A. Replace only second '# Change here' line with result.append(current.val)

B. Replace both '# Change here' lines with result.append(current.val)

C. Replace only first '# Change here' line with result.append(current.val)

D. Replace both '# Change here' lines with print(current.val)

Solution

1. Step 1: Identify where nodes are visited

   In Morris traversal, nodes are visited and printed in two places: when left is None and after removing thread.

2. Step 2: Replace print with appending to list

   To collect values, replace both print statements with result.append(current.val) to capture all visited nodes.

3. Final Answer:

   Replace both '# Change here' lines with result.append(current.val) -> Option B

4. Quick Check:

   Collect all visited nodes in list [OK]

Hint: Append values at both visit points to collect all nodes [OK]

Common Mistakes:

• Appending only once misses some nodes
• Leaving print statements causes unwanted output
• Changing traversal logic breaks correctness