Morris Traversal Inorder Without Stack in DSA Rust - 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 memory like a stack or recursion. It temporarily changes the tree structure by creating links to predecessor nodes, allowing traversal with constant space. 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 environments. Morris Traversal solves this by using no extra space, making it efficient and practical for memory-constrained systems. It also deepens understanding of tree structures and pointer manipulation.

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 tree traversal optimizations, threaded binary trees, and advanced tree algorithms that manipulate pointers for efficiency.

Mental Model

Core Idea

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

Think of it like...

Imagine walking through a maze where you leave temporary breadcrumbs to find your way back without carrying a map or notes. Once you finish, you pick up all breadcrumbs, leaving the maze unchanged.

Binary Tree Node Structure:

       [Current Node]
          /      \
    [Left]      [Right]

Traversal Steps:

1. If left child is null, visit current and move right.
2. Else, find rightmost node in left subtree (predecessor).
3. If predecessor's right is null, link it to current and move left.
4. If predecessor's right points to current, remove link, visit current, move right.

Flowchart:

┌─────────────┐
│ Start at root│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Left child? │
└──────┬──────┘
   No  │  Yes
       ▼     ▼
 Visit node  Find predecessor
   │          │
   ▼          ▼
 Move right  Link or unlink
             │
             ▼
          Move left or right

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Inorder Traversal

Concept: Learn how inorder traversal visits nodes in left-root-right order using recursion or stack.

Inorder traversal means visiting the left subtree, then the current node, then the right subtree. Normally, recursion or a stack keeps track of nodes to visit later. For example, for a tree: 2 / \ 1 3 The inorder traversal visits nodes in order: 1, 2, 3.

Result

Visiting nodes in sorted order for binary search trees, e.g., 1 -> 2 -> 3 -> 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.

Recursion uses the call stack, which can grow up to the tree height, risking stack overflow for deep trees. Using an explicit stack also consumes memory proportional to tree height. This can be inefficient or impossible in memory-limited environments.

Result

Traversal requires O(h) extra space, where h is tree height.

Knowing the memory cost motivates finding traversal methods that use constant space.

3

Intermediate

Finding the Inorder Predecessor Node

🤔Before reading on: do you think the inorder predecessor is always the left child? Commit to yes or no.

Concept: Learn to find the rightmost node in the left subtree, called the inorder predecessor.

For a current node, its inorder predecessor is the rightmost node in its left subtree. This node comes just before the current node in inorder traversal. To find it, start at left child and keep moving right until no right child exists or the right child is the current node (in case of temporary link).

Result

Ability to identify the predecessor node needed for Morris Traversal linking.

Understanding predecessor nodes is key to creating temporary links that enable traversal without extra memory.

4

Intermediate

Creating and Removing Temporary Links

🤔Before reading on: do you think temporary links permanently change the tree structure? Commit to yes or no.

Concept: Use the predecessor's right pointer to temporarily link back to the current node, then remove it after visiting.

If the predecessor's right pointer is null, set it to current node to remember the path back. When revisiting the predecessor, detect the link, remove it, visit current node, and move right. This avoids using stack or recursion by simulating the return path.

Result

Traversal proceeds without extra memory, and tree is restored after traversal.

Temporary links cleverly simulate the call stack, enabling constant space traversal.

5

Intermediate

Implementing Morris Traversal Algorithm

🤔Before reading on: do you think Morris Traversal visits nodes in the same order as recursive inorder? Commit to yes or no.

Concept: Combine predecessor finding and temporary linking to traverse the tree inorder without stack or recursion.

Algorithm steps: 1. Initialize current as root. 2. While current is not null: a. If current.left is null, visit current and move current to current.right. b. Else, find predecessor. i. If predecessor.right is null, set predecessor.right = current, move current to current.left. ii. Else, set predecessor.right = null, visit current, move current to current.right. This visits nodes in inorder sequence without extra memory.

Result

Inorder traversal output matches recursive method, e.g., 1 -> 2 -> 3 -> null.

Combining pointer manipulation with traversal logic achieves memory-efficient inorder traversal.

6

Advanced

Rust Implementation of Morris Traversal

🤔Before reading on: do you think Rust's ownership rules complicate pointer manipulation in Morris Traversal? Commit to yes or no.

Concept: Implement Morris Traversal in Rust, handling mutable references and optional pointers safely.

Rust code example: ```rust use std::rc::Rc; use std::cell::RefCell; #[derive(Debug)] struct TreeNode { val: i32, left: Option>>, right: Option>>, } fn morris_inorder(root: Option>>) { let mut current = root.clone(); while let Some(curr_node) = current.clone() { let left = curr_node.borrow().left.clone(); if left.is_none() { print!("{} -> ", curr_node.borrow().val); current = curr_node.borrow().right.clone(); } else { let mut predecessor = left.clone(); while let Some(pred_node) = predecessor.clone() { let right = pred_node.borrow().right.clone(); if right.is_none() || right.as_ref() == Some(&curr_node) { break; } predecessor = right; } if let Some(pred_node) = predecessor { if pred_node.borrow().right.is_none() { pred_node.borrow_mut().right = Some(curr_node.clone()); current = curr_node.borrow().left.clone(); } else { pred_node.borrow_mut().right = None; print!("{} -> ", curr_node.borrow().val); current = curr_node.borrow().right.clone(); } } } } println!("null"); } ``` This code uses Rc and RefCell to manage shared mutable references safely in Rust.

Result

Prints nodes in inorder without stack or recursion, e.g., 1 -> 2 -> 3 -> null.

Understanding Rust's ownership and borrowing is crucial to safely implement pointer-based algorithms like Morris Traversal.

7

Expert

Handling Edge Cases and Tree Restoration

🤔Before reading on: do you think Morris Traversal can leave the tree modified if interrupted? Commit to yes or no.

Concept: Ensure that temporary links are always removed to restore the tree, even in edge cases like empty trees or single nodes.

Morris Traversal must carefully remove all temporary links to avoid corrupting the tree. For empty trees, traversal ends immediately. For single-node trees, no links are created. If interrupted mid-traversal, the tree may remain modified, so Morris Traversal is best used in controlled environments or with full traversal completion.

Result

Tree structure remains unchanged after traversal, preserving data integrity.

Knowing the importance of restoring the tree prevents subtle bugs and data corruption in production.

Under the Hood

Morris Traversal works by temporarily modifying the tree's right pointers of inorder predecessor nodes 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 revisits a predecessor, it detects the temporary link, removes it, and visits the current node. This pointer manipulation allows inorder traversal using only O(1) extra space.

Why designed this way?

Traditional inorder traversal uses recursion or stacks, which consume memory proportional to tree height. Morris Traversal was designed to optimize space by reusing existing tree pointers to remember traversal paths. This approach trades temporary tree modification for memory efficiency, which is valuable in constrained environments. Alternatives like threaded binary trees inspired this method, but Morris Traversal applies it dynamically without permanent tree changes.

Traversal Flow:

[Current Node]
     |
     v
[Check Left Child]
     |
     +-- No --> Visit Node --> Move Right
     |
     +-- Yes --> Find Predecessor
                  |
                  v
          [Predecessor Right]
             |
             +-- Null --> Link to Current --> Move Left
             |
             +-- Points to Current --> Remove Link --> Visit Node --> Move Right

Myth Busters - 4 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 them before finishing, leaving the tree unchanged.

Why it matters: Believing the tree is permanently changed may prevent using Morris Traversal in applications where tree integrity is critical.

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

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

Reality: Morris Traversal may be slower due to extra pointer manipulations and repeated visits to nodes when finding predecessors.

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

Quick: Can Morris Traversal be used on any binary tree without restrictions? Commit to yes or no.

Common Belief: Morris Traversal works on all binary trees without any special conditions.

Reality: Morris Traversal requires the ability to modify pointers temporarily, so it cannot be used on immutable trees or trees where pointer changes are forbidden.

Why it matters: Trying to use Morris Traversal on immutable data structures will cause errors or undefined behavior.

Quick: Does Morris Traversal use extra memory proportional to tree height? Commit to yes or no.

Common Belief: Morris Traversal uses extra memory like recursion or stack.

Reality: Morris Traversal uses only constant extra memory, O(1), by reusing tree pointers.

Why it matters: Misunderstanding memory usage can lead to missing the main advantage of Morris Traversal.

Expert Zone

1

Morris Traversal's temporary links create a threaded binary tree structure only during traversal, which is removed afterward, unlike permanent threaded trees.

2

The algorithm visits some nodes twice: once to create the link and once to remove it, which affects runtime but not space complexity.

3

Implementing Morris Traversal in languages with strict ownership (like Rust) requires careful handling of mutable references and optional pointers to avoid runtime errors.

When NOT to use

Avoid Morris Traversal when tree nodes are immutable or shared across threads without synchronization, as temporary pointer changes can cause data races or corruption. Also, if traversal speed is critical and extra memory is available, recursive or stack-based traversal may be faster and simpler.

Production Patterns

Morris Traversal is used in embedded systems or memory-constrained environments where recursion is risky. It also appears in interview problems to test pointer manipulation skills. In production, it can be combined with other tree algorithms that require constant space traversal or used to implement threaded binary trees dynamically.

Connections

Threaded Binary Trees

Morris Traversal dynamically creates temporary threads similar to permanent threaded binary trees.

Understanding threaded binary trees helps grasp how Morris Traversal uses pointers to simulate stack behavior without extra memory.

Call Stack in Recursion

Morris Traversal simulates the call stack by using tree pointers instead of memory structures.

Recognizing that recursion uses a call stack clarifies how Morris Traversal replaces it with pointer links.

Breadcrumb Navigation in Web Browsers

Both use temporary markers to remember paths without storing full history externally.

Seeing how breadcrumbs help users navigate back without full history storage parallels Morris Traversal's temporary links for backtracking.

Common Pitfalls

#1 Not removing temporary links after traversal.

Wrong approach:

if predecessor.right.is_none() {
predecessor.right = Some(current);
current = current.left;
} else {
// Missing removal of link here
print!("{} -> ", current.val);
current = current.right;
}

Correct approach:

if predecessor.right.is_none() {
predecessor.right = Some(current);
current = current.left;
} else {
predecessor.right = None; // Remove link
print!("{} -> ", current.val);
current = current.right;
}

Root cause:

Forgetting to remove the temporary link causes the tree to remain modified, corrupting structure.

#2 Assuming left child is always predecessor.

Wrong approach:

let predecessor = current.left; // Using left child directly without finding rightmost node

Correct approach:

let mut predecessor = current.left;
while predecessor.right.is_some() && predecessor.right != Some(current) {
predecessor = predecessor.right;
}

Root cause:

Misunderstanding the definition of inorder predecessor leads to incorrect traversal paths.

#3 Using Morris Traversal on immutable tree nodes.

Wrong approach:

// Immutable tree nodes with no pointer modification allowed
// Attempting to set predecessor.right = current causes compile error or panic

Correct approach:

// Use recursive or stack-based traversal for immutable trees
fn inorder_recursive(node: Option<&Node>) {
if let Some(n) = node {
inorder_recursive(n.left.as_ref());
print!("{} -> ", n.val);
inorder_recursive(n.right.as_ref());
}
}

Root cause:

Trying to modify immutable data structures violates language safety and causes errors.

Key Takeaways

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

It works by creating and removing temporary links from a node's inorder predecessor back to the node, simulating the call stack.

This method preserves the original tree structure by restoring all changes after traversal completes.

Implementing Morris Traversal requires careful pointer manipulation and understanding of tree structure, especially in languages with strict ownership rules.

While memory efficient, Morris Traversal may be slower than recursive methods and is unsuitable for immutable or shared trees.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to traditional methods?

easy

A. It is faster than all other traversal methods

B. It requires a special tree structure

C. It only works on binary search trees

D. It uses no extra space like stack or recursion

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal modifies tree links temporarily to avoid using stack or recursion.

2. Step 2: Compare with traditional methods

   Traditional inorder traversal uses stack or recursion which require extra space. Morris Traversal uses O(1) extra space.

3. Final Answer:

   It uses no extra space like stack or recursion -> Option D

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Remember Morris uses threaded links, no stack needed [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Assuming it only works on BSTs
• Confusing it with recursive traversal

2. Which Rust code snippet correctly initializes a mutable pointer to the root node for Morris Traversal?

easy

A. let mut current = root.as_ref();

B. let mut current = root.as_mut();

C. let current = root.clone();

D. let current = &root;

Solution

1. Step 1: Identify mutable pointer requirement

   Morris Traversal modifies tree links, so mutable access is needed.

2. Step 2: Choose correct Rust method

   root.as_mut() gives mutable reference, root.as_ref() is immutable, clone copies, &root is immutable reference.

3. Final Answer:

   let mut current = root.as_mut(); -> Option B

4. Quick Check:

   Mutable reference needed = let mut current = root.as_mut(); [OK]

Hint: Use as_mut() for mutable access in Rust trees [OK]

Common Mistakes:

• Using as_ref() which is immutable
• Cloning unnecessarily
• Using immutable references when mutation is needed

3. Given the following Rust code for Morris Traversal on a binary tree with nodes 1 (root), 2 (left child), and 3 (right child), what is the printed inorder sequence?

struct Node {
    val: i32,
    left: Option,
    right: Option,
}

fn morris_inorder(root: &mut Option) {
    let mut current = root.as_mut();
    while let Some(node) = current {
        if node.left.is_none() {
            print!("{} ", node.val);
            current = node.right.as_mut();
        } else {
            let mut pre = node.left.as_mut();
            while let Some(p) = pre {
                if p.right.is_some() && p.right.as_ref().unwrap().val != node.val {
                    pre = p.right.as_mut();
                } else {
                    break;
                }
            }
            if pre.is_some() && pre.as_ref().unwrap().right.is_none() {
                pre.as_mut().unwrap().right = Some(Box::new(Node { val: node.val, left: None, right: None }));
                current = node.left.as_mut();
            } else {
                pre.as_mut().unwrap().right = None;
                print!("{} ", node.val);
                current = node.right.as_mut();
            }
        }
    }
}

medium

A. 2 1 3

B. 1 2 3

C. 3 1 2

D. 1 3 2

Solution

1. Step 1: Understand tree structure

   Root=1, left=2, right=3. Inorder is left-root-right.

2. Step 2: Trace Morris traversal output

   Visit left (2), then root (1), then right (3). So output is "2 1 3".

3. Final Answer:

   2 1 3 -> Option A

4. Quick Check:

   Inorder traversal = 2 1 3 [OK]

Hint: Inorder = left, root, right; Morris prints in this order [OK]

Common Mistakes:

• Confusing preorder or postorder output
• Not restoring links causing infinite loops
• Misreading tree structure

4. In the following Rust snippet for Morris Traversal, what is the main bug causing an infinite loop?

fn morris_inorder_bug(root: &mut Option) {
    let mut current = root.as_mut();
    while let Some(node) = current {
        if node.left.is_some() {
            let mut pre = node.left.as_mut();
            while pre.is_some() && pre.as_ref().unwrap().right.is_some() {
                pre = pre.unwrap().right.as_mut();
            }
            if pre.is_some() {
                pre.as_mut().unwrap().right = Some(Box::new(Node { val: node.val, left: None, right: None }));
                current = node.left.as_mut();
            }
        } else {
            print!("{} ", node.val);
            current = node.right.as_mut();
        }
    }
}

medium

A. Using immutable references instead of mutable

B. Incorrectly printing node values

C. Not removing temporary threaded links after use

D. Missing base case for empty tree

Solution

1. Step 1: Analyze threaded link handling

   Code creates temporary right links but never removes them.

2. Step 2: Understand infinite loop cause

   Without removing threaded links, traversal cycles endlessly on same nodes.

3. Final Answer:

   Not removing temporary threaded links after use -> Option C

4. Quick Check:

   Threaded links must be removed to avoid loops [OK]

Hint: Always remove threaded links after visiting left subtree [OK]

Common Mistakes:

• Ignoring threaded link removal
• Confusing printing with traversal logic
• Not using mutable references properly

5. You want to modify Morris Traversal inorder code in Rust to collect node values into a vector instead of printing. Which change correctly implements this without breaking the traversal logic?

fn morris_inorder_collect(root: &mut Option) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = root.as_mut();
    while let Some(node) = current {
        if node.left.is_none() {
            // Change here
            current = node.right.as_mut();
        } else {
            let mut pre = node.left.as_mut();
            while let Some(p) = pre {
                if p.right.is_some() && p.right.as_ref().unwrap().val != node.val {
                    pre = p.right.as_mut();
                } else {
                    break;
                }
            }
            if pre.is_some() && pre.as_ref().unwrap().right.is_none() {
                pre.as_mut().unwrap().right = Some(Box::new(Node { val: node.val, left: None, right: None }));
                current = node.left.as_mut();
            } else {
                pre.as_mut().unwrap().right = None;
                // Change here
                current = node.right.as_mut();
            }
        }
    }
    result
}

hard

A. Replace both comments with result.push(node.val);

B. Replace first comment with print!("{} ", node.val); second with result.push(node.val);

C. Replace first comment with result.push(node.val); second with print!("{} ", node.val);

D. Replace both comments with print!("{} ", node.val);

Solution

1. Step 1: Identify where node values are processed

   Values are printed at two places: when left is None and after restoring threaded links.

2. Step 2: Replace printing with pushing to vector

   To collect values, replace both prints with result.push(node.val) to keep traversal logic intact.

3. Final Answer:

   Replace both comments with result.push(node.val); -> Option A

4. Quick Check:

   Collect values by pushing at both print points [OK]

Hint: Push values where prints occur to collect inorder sequence [OK]

Common Mistakes:

• Mixing print and push causing partial collection
• Pushing only once missing some nodes
• Breaking traversal by adding prints