Morris Traversal Inorder Without Stack in DSA Python

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 tree you visited, so you can return without losing your way or carrying a map.

    4
   / \
  2   5
 / \
1   3

No extra stack, just temporary links (threads) to predecessors.

Dry Run Walkthrough

Input: Binary tree: 4 / \ 2 5 / \ 1 3 Perform inorder traversal using Morris Traversal

Goal: Print nodes in inorder sequence: 1 2 3 4 5 without using stack or recursion

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

4 ↑ -> 2 -> 1 -> null and 4 -> 5 -> null

Why: We need to find the rightmost node in 4's left subtree to create a temporary link

Step 2: Predecessor is 3, create temporary link from 3.right to 4

3.right -> 4 (thread created)
4 ↑ -> 2 -> 1 -> null
4 -> 5 -> null

Why: This thread helps us return to 4 after visiting left subtree

Step 3: Move current to left child (2)

2 ↑ -> 1 -> null
3.right -> 4 (thread)
4 -> 5 -> null

Why: Traverse left subtree first

Step 4: Find predecessor of 2 (which is 1), create thread 1.right -> 2

1.right -> 2 (thread)
2 ↑ -> null
3.right -> 4
4 -> 5 -> null

Why: Thread to return to 2 after visiting 1

Step 5: Move current to left child (1)

1 ↑ -> null
2 -> null
3.right -> 4
4 -> 5 -> null

Why: Go to leftmost node

Step 6: 1 has no left child, print 1 and move to 1.right (which is thread to 2)

Printed: 1
Current moves to 2 via thread
2 ↑ -> null

Why: Visit node and follow thread back to parent

Step 7: Remove thread 1.right, print 2, move to 2.right (3)

Thread 1.right removed
Printed: 2
Current at 3 ↑
3.right -> 4 (thread)

Why: Restore tree and continue inorder

Step 8: 3 has no left child, print 3, move to 3.right (thread to 4)

Printed: 3
Current moves to 4 via thread
4 ↑ -> 5

Why: Visit node and follow thread back to parent

Step 9: Remove thread 3.right, print 4, move to 4.right (5)

Thread 3.right removed
Printed: 4
Current at 5 ↑

Why: Restore tree and continue

Step 10: 5 has no left child, print 5, move to 5.right (null)

Printed: 5
Current is null, traversal ends

Why: Visit last node and finish

Result:

1 -> 2 -> 3 -> 4 -> 5 -> null
Printed sequence: 1 2 3 4 5

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def morris_inorder(root):
    curr = root
    result = []
    while curr:
        if curr.left is None:
            result.append(curr.val)  # visit node with no left child
            curr = curr.right       # move to right child
        else:
            pred = curr.left
            while pred.right and pred.right != curr:
                pred = pred.right  # find inorder predecessor
            if pred.right is None:
                pred.right = curr  # create thread
                curr = curr.left   # move to left child
            else:
                pred.right = None  # remove thread
                result.append(curr.val)  # visit node
                curr = curr.right  # move to right child
    print(' '.join(str(x) for x in result))

# Driver code
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)
morris_inorder(root)

while curr:

continue traversal until all nodes visited

if curr.left is None:

if no left child, visit node and move right

pred = curr.left while pred.right and pred.right != curr: pred = pred.right

find inorder predecessor in left subtree

if pred.right is None: pred.right = curr curr = curr.left

create temporary thread and move left

else: pred.right = None result.append(curr.val) curr = curr.right

remove thread, visit node, move right

Output

1 2 3 4 5

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 changed temporarily

vs Alternative: Compared to recursive or stack-based inorder traversal which uses O(h) space, Morris traversal saves memory by using threads

Edge Cases

Empty tree (root is None)

No output, traversal ends immediately

DSA Python

while curr:

Tree with single node

Prints the single node value correctly

DSA Python

if curr.left is None:

Tree with no left children (all right skewed)

Visits nodes in order without creating threads

DSA Python

if curr.left is None:

When to Use This Pattern

When asked to do inorder traversal without extra memory like stack or recursion, think of Morris Traversal which uses temporary threads to predecessors.

Common Mistakes

Mistake: Not removing the temporary thread after visiting the node, causing infinite loops
Fix: Always remove the thread by setting predecessor.right = None after returning to the node

Mistake: Not checking if predecessor.right already points to current node before creating thread
Fix: Check if predecessor.right is None before creating thread, else remove it

Summary

Morris Traversal prints inorder nodes without stack or recursion by creating temporary threads.

Use it when you want inorder traversal with O(1) extra space.

The key insight is to link the inorder predecessor's right pointer to the current node temporarily to return after left subtree.

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