Morris Traversal Inorder Without Stack in DSA Rust - 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

↓

Repeat until current is None

This flow shows how Morris Traversal visits nodes without stack by creating temporary threads to predecessors and removing them after visiting.

Execution Sample

DSA Rust

fn morris_inorder(root: Option<&Box<TreeNode>>) {
    let mut current = root;
    while current.is_some() {
        let node = current.as_ref().unwrap();
        if node.left.is_none() {
            println!("{}", node.val);
            current = node.right.as_ref();
        } else {
            // Find predecessor
            let mut predecessor = node.left.as_ref();
            while predecessor.unwrap().right.is_some() && predecessor.unwrap().right.as_ref() != current {
                predecessor = predecessor.unwrap().right.as_ref();
            }
            if predecessor.unwrap().right.is_none() {
                // Make thread
                unsafe {
                    let pred_mut = &mut *(predecessor.unwrap() as *const _ as *mut TreeNode);
                    pred_mut.right = current.cloned();
                }
                current = node.left.as_ref();
            } else {
                // Remove thread
                unsafe {
                    let pred_mut = &mut *(predecessor.unwrap() as *const _ as *mut TreeNode);
                    pred_mut.right = None;
                }
                println!("{}", node.val);
                current = node.right.as_ref();
            }
        }
    }
}

This code traverses a binary tree inorder without using stack or recursion by creating temporary links.

Execution Table

Step	Operation	Current Node	Predecessor	Thread Created/Removed	Visual State
1	Start at root	1	None	None	1 / \ 2 3
2	Current.left is not None	1	2	Create thread: 2.right = 1	1 / \ 2→1 3 (thread from 2 to 1)
3	Move current to left	2	None	None	1 / \ 2→1 3
4	Current.left is None	2	None	None	1 / \ 2→1 3
5	Visit current node	2	None	None	Visited: 2
6	Move current to right	1	None	None	1 / \ 2→1 3
7	Predecessor.right is thread to current	1	2	Remove thread: 2.right = None	1 / \ 2 3 (thread removed)
8	Visit current node	1	None	None	Visited: 2, 1
9	Move current to right	3	None	None	1 / \ 2 3
10	Current.left is None	3	None	None	1 / \ 2 3
11	Visit current node	3	None	None	Visited: 2, 1, 3
12	Move current to right	None	None	None	Traversal complete
13	Current is None	None	None	None	End traversal

💡 Traversal ends when current becomes None after visiting all nodes.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 9	Final
current	root (1)	1	2	1	3	None
predecessor	None	2	None	None	None	None
thread	None	Created (2.right=1)	Created	Created	None	None
visited_nodes	[]	[]	[]	[2]	[2,1]	[2,1,3]

Key Moments - 3 Insights

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

Creating a thread lets us return to the current node after finishing the left subtree without using a stack, as shown in step 2 and step 7 where the thread is created and later removed.

What happens when current.left is None?

When current.left is None (steps 4 and 10), we visit the current node and move to current.right directly, because there is no left subtree to process.

How do we know when traversal ends?

Traversal ends when current becomes None (step 12 and 13), meaning we have visited all nodes and there are no more nodes to process.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'current' after step 3?

A Node 1

B Node 3

C Node 2

D None

💡 Hint

Check the 'current' column in the execution_table row for step 3.

At which step is the thread from predecessor.right to current removed?

A Step 7

B Step 5

C Step 2

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

B Traversal would visit nodes directly without creating threads

C Traversal would not visit any nodes

D Traversal would get stuck in an infinite loop

💡 Hint

Refer to steps where current.left is None and no threads are created.

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Uses threaded binary tree links to avoid stack/recursion
- For each node, find predecessor in left subtree
- Create thread from predecessor.right to current if none
- Visit node when left subtree done or no left child
- Remove thread after visiting
- Ends when current is None

Full Transcript

Morris Traversal visits nodes inorder without using stack or recursion by temporarily modifying the tree. 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 (predecessor) in the left subtree. If the predecessor's right pointer is None, a thread is created to the current node, and traversal moves to the left child. If the thread already exists, it is removed, the current node is visited, and traversal moves to the right child. This process repeats until all nodes are visited and current becomes None. This method saves memory by avoiding stack usage and uses temporary links to remember the path back to nodes.

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