Morris Traversal Inorder Without Stack in DSA Python - Deep Dive

Overview - Morris Traversal Inorder Without Stack

What is it?

Morris Traversal is a way to visit all nodes of a binary tree in order without using extra space like a stack or recursion. It temporarily changes the tree structure by creating links to predecessors, allowing traversal with only constant extra memory. After visiting nodes, it restores the tree to its original shape. This method is useful when memory is limited or recursion is not desired.

Why it matters

Without Morris Traversal, inorder tree traversal usually requires extra memory for a stack or recursion, which can be costly for large trees or limited memory devices. Morris Traversal solves this by using the tree itself to keep track of where to go next, saving memory and improving efficiency. This can make programs faster and more memory-friendly, especially in embedded systems or large data processing.

Where it fits

Before learning Morris Traversal, you should understand binary trees and basic inorder traversal using recursion or a stack. After mastering Morris Traversal, you can explore other space-efficient tree traversals and advanced tree algorithms like threaded binary trees or tree threading concepts.

Mental Model

Core Idea

Morris Traversal visits nodes by temporarily linking each node's predecessor back to it, enabling inorder traversal without extra memory.

Think of it like...

Imagine walking through a maze where you leave temporary arrows on walls pointing back to where you came from, so you can return without getting lost or carrying a map.

Binary Tree Node Structure:

       4
      / \
     2   5
    / \
   1   3

Traversal Steps:

1. Start at root (4).
2. Find predecessor of current node (rightmost node in left subtree).
3. If predecessor's right is null, link it to current node and move left.
4. If predecessor's right points to current node, remove link, visit current, move right.

Flow:

Current Node
   |
   v
Find Predecessor
   |
   v
Link or Visit
   |
   v
Move Left or Right

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Inorder Traversal

Concept: Learn the basic inorder traversal that visits left child, node, then right child.

Inorder traversal means visiting nodes in this order: left subtree, current node, right subtree. For example, in a binary tree with root 4, left child 2, and right child 5, the inorder sequence is 1, 2, 3, 4, 5 if the left subtree has nodes 1 and 3. Usually, this is done using recursion or a stack to remember nodes.

Result

Inorder traversal outputs nodes in sorted order for binary search trees: 1 -> 2 -> 3 -> 4 -> 5 -> null

Understanding the order of visiting nodes is essential before optimizing traversal methods.

2

Foundation

Limitations of Recursion and Stack Usage

Concept: Recognize that recursion and stacks use extra memory proportional to tree height.

When using recursion or a stack, each call or push stores information about nodes to visit later. For a tree with height h, this can use up to O(h) extra memory. In very deep trees, this can cause stack overflow or high memory use, which is inefficient or impossible in some systems.

Result

Traversal uses extra memory: O(h) space for stack or recursion calls.

Knowing the memory cost of common traversal methods motivates the need for space-efficient alternatives.

3

Intermediate

Concept of Threaded Binary Trees

Concept: Introduce the idea of using unused right pointers to link back to predecessors.

A threaded binary tree uses null right pointers to point to the inorder successor or predecessor. This threading allows traversal without stack or recursion by following these links. Morris Traversal temporarily creates such threads during traversal and removes them afterward.

Result

Tree temporarily gains extra links (threads) to enable traversal without extra memory.

Understanding threading reveals how Morris Traversal cleverly uses the tree's structure to save memory.

4

Intermediate

Finding Predecessors and Creating Temporary Links

🤔Before reading on: do you think the predecessor is always the left child or can it be deeper? Commit to your answer.

Concept: Learn how to find the rightmost node in the left subtree (predecessor) and link it back to the current node.

For each node, if it has a left child, find its inorder predecessor by going to the left child and then repeatedly to the right child until no more right children exist or the right child is the current node. If the predecessor's right pointer is null, set it to point to the current node (creating a thread), then move to the left child. This thread helps return to the current node after finishing the left subtree.

Result

Temporary links allow returning to nodes without stack or recursion.

Knowing how to find and link predecessors is key to traversing without extra memory.

5

Intermediate

Restoring Tree and Visiting Nodes Correctly

🤔Before reading on: do you think the temporary links should stay after traversal? Commit to yes or no.

Concept: Understand how to detect and remove temporary links and visit nodes in correct order.

When the predecessor's right pointer points back to the current node, it means the left subtree is fully visited. Remove this temporary link by setting predecessor's right to null, visit the current node (print or process it), then move to the right child. If no left child exists, visit the current node and move right directly.

Result

Tree structure is restored and nodes are visited in inorder sequence.

Restoring the tree ensures no permanent changes, making Morris Traversal safe and reversible.

6

Advanced

Implementing Morris Traversal in Python

🤔Before reading on: do you think Morris Traversal requires recursion or stack in code? Commit to yes or no.

Concept: Write complete Python code to perform Morris inorder traversal without extra memory.

```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def morris_inorder(root): result = [] current = root while current: if current.left is None: result.append(current.val) # Visit node 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 # Create thread current = current.left else: predecessor.right = None # Remove thread result.append(current.val) # Visit node current = current.right return result # Example usage: # Construct tree: 4 # / \ # 2 5 # / \ # 1 3 root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(5)) print(morris_inorder(root)) # Output: [1, 2, 3, 4, 5] ```

Result

[1, 2, 3, 4, 5]

Seeing the full code clarifies how Morris Traversal works step-by-step without recursion or stack.

7

Expert

Performance and Edge Cases of Morris Traversal

🤔Before reading on: do you think Morris Traversal always improves speed over recursion? Commit to yes or no.

Concept: Analyze time complexity, tree modifications, and cases where Morris Traversal may be less ideal.

Morris Traversal runs in O(n) time, visiting each node at most twice. It uses O(1) extra space but modifies the tree temporarily. For very large or unbalanced trees, it avoids stack overflow. However, it may be slower in practice due to extra pointer changes. Also, it requires the tree to be mutable and not shared concurrently. In read-only or concurrent environments, recursion or stack is safer.

Result

Morris Traversal is space-efficient but may trade off some speed and safety in certain cases.

Knowing trade-offs helps decide when Morris Traversal is the best choice in real systems.

Under the Hood

Morris Traversal works by temporarily changing the tree's right pointers of inorder predecessors to point back to the current node. This creates a threaded path that simulates the call stack or explicit stack used in recursion. When the traversal returns to a node via this thread, it removes the thread and visits the node. This process repeats until all nodes are visited, ensuring O(1) extra space usage.

Why designed this way?

It was designed to overcome the memory overhead of recursion and stacks in tree traversal. By using the tree's null pointers as temporary links, it avoids extra data structures. Alternatives like recursion are simpler but use more memory; Morris Traversal trades complexity for space efficiency.

Traversal Flow:

+-------------------+
| Start at root     |
+---------+---------+
          |
          v
+-------------------+
| Check left child   |
+---------+---------+
          |
   +------+------+
   |             |
   v             v
No left child  Has left child
   |             |
   v             v
Visit node   Find predecessor
   |             |
   v             v
Move right  Create or remove thread
   |             |
   +-------------+
          |
          v
     Repeat until
     current is null

Myth Busters - 3 Common Misconceptions

Quick: Does Morris Traversal permanently change the tree structure? Commit to yes or no.

Common Belief: Morris Traversal permanently modifies the tree by changing pointers.

Reality: Morris Traversal only temporarily changes pointers and restores the tree to its original form after traversal.

Why it matters: If you believe the tree is permanently changed, you might avoid using Morris Traversal or worry about data corruption unnecessarily.

Quick: Does Morris Traversal use recursion or a stack internally? Commit to yes or no.

Common Belief: Morris Traversal still uses recursion or a stack behind the scenes.

Reality: Morris Traversal uses no recursion or stack; it uses the tree's structure itself to track traversal.

Why it matters: Misunderstanding this leads to missing the main advantage of Morris Traversal: O(1) extra space.

Quick: Is Morris Traversal always faster than recursive traversal? Commit to yes or no.

Common Belief: Morris Traversal is always faster because it uses less memory.

Reality: Morris Traversal may be slower due to extra pointer manipulations despite saving memory.

Why it matters: Assuming it is always faster can lead to poor performance choices in time-critical applications.

Expert Zone

1

Morris Traversal requires the tree to be mutable; it cannot be used on immutable or shared trees without risking corruption.

2

The traversal visits some nodes twice: once when creating the thread and once when removing it, which affects performance.

3

In threaded binary trees, threads are permanent, but Morris Traversal creates and removes threads dynamically during traversal.

When NOT to use

Avoid Morris Traversal when the tree is immutable, shared across threads, or when pointer modifications are forbidden. Use recursive or iterative stack-based traversal instead in these cases.

Production Patterns

Morris Traversal is used in embedded systems or memory-constrained environments where recursion is risky. It is also used in interview problems to demonstrate space-efficient traversal and in systems where temporary tree modifications are acceptable.

Connections

Threaded Binary Trees

Morris Traversal builds on the idea of threaded binary trees by temporarily creating threads during traversal.

Understanding threaded trees helps grasp how Morris Traversal uses temporary links to avoid extra memory.

Inorder Tree Traversal

Morris Traversal is an alternative method to perform inorder traversal without recursion or stack.

Knowing standard inorder traversal clarifies what Morris Traversal optimizes and how it preserves node visiting order.

Maze Navigation

Both involve leaving temporary markers to avoid getting lost and to return to previous points without extra memory.

Recognizing this pattern in different fields shows how temporary links or markers can replace external memory.

Common Pitfalls

#1 Not removing temporary threads after traversal.

Wrong approach:

def morris_inorder(root):
current = root
while current:
if current.left:
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:
# Missing removal of thread here
print(current.val)
current = current.right
else:
print(current.val)
current = current.right

Correct approach:

def morris_inorder(root):
current = root
while current:
if current.left:
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 # Remove thread
print(current.val)
current = current.right
else:
print(current.val)
current = current.right

Root cause:

Forgetting to restore the tree by removing temporary links leads to corrupted tree structure.

#2 Assuming Morris Traversal works on immutable trees.

Wrong approach:

# Using Morris Traversal on an immutable tree structure (e.g., tuples or frozen nodes) causes errors or undefined behavior.

Correct approach:

# Use recursive or stack-based traversal for immutable trees to avoid modifying structure.

Root cause:

Morris Traversal relies on modifying pointers; immutable data structures cannot support this.

Key Takeaways

Morris Traversal enables inorder traversal of binary trees using only constant extra space by temporarily modifying the tree.

It works by creating and removing temporary threads from a node's inorder predecessor back to the node itself.

This method avoids recursion and stacks, making it memory-efficient but requires a mutable tree.

Understanding how to find predecessors and manage threads is essential to implementing Morris Traversal correctly.

While space-efficient, Morris Traversal may be slower and is unsuitable for immutable or shared trees.

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