Morris Traversal Inorder Without Stack in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a simple tree

What is the output of the Morris inorder traversal on the following binary tree?

Tree structure:
2
/ \
1 3

Assume the traversal prints node values in order.

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn morris_inorder(root: &mut Option<Box<Node>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = root.as_mut().map(|b| &mut **b);
    while let Some(node) = current {
        if node.left.is_none() {
            result.push(node.val);
            current = node.right.as_mut().map(|b| &mut **b);
        } else {
            let mut pre = node.left.as_mut().map(|b| &mut **b).unwrap();
            while pre.right.is_some() && pre.right.as_ref().unwrap().val != node.val {
                pre = pre.right.as_mut().map(|b| &mut **b).unwrap();
            }
            if pre.right.is_none() {
                pre.right = Some(Box::new(Node { val: node.val, left: None, right: None }));
                current = node.left.as_mut().map(|b| &mut **b);
            } else {
                pre.right = None;
                result.push(node.val);
                current = node.right.as_mut().map(|b| &mut **b);
            }
        }
    }
    result
}

fn main() {
    let mut root = Some(Box::new(Node {
        val: 2,
        left: Some(Box::new(Node { val: 1, left: None, right: None })),
        right: Some(Box::new(Node { val: 3, left: None, right: None })),
    }));
    let output = morris_inorder(&mut root);
    println!("{:?}", output);
}

A [2, 1, 3]

B [3, 2, 1]

C [1, 3, 2]

D [1, 2, 3]

💡 Hint

Remember inorder traversal visits left subtree, then node, then right subtree.

Morris inorder traversal visits nodes in ascending order for a BST. The tree has nodes 1, 2, 3 with 2 as root, so output is [1, 2, 3].

🧠 Conceptual

intermediate

Why Morris Traversal uses threading?

Why does Morris inorder traversal create temporary links (threads) in the binary tree during traversal?

A To store node values in a separate array for output.

B To permanently change the tree structure for faster future traversals.

C To avoid using recursion or stack by temporarily linking nodes to their inorder successor.

D To balance the tree dynamically during traversal.

💡 Hint

Think about how Morris traversal avoids extra memory usage.

Morris traversal creates temporary threads to the inorder successor to avoid recursion or stack, enabling O(1) space traversal.

🔧 Debug

advanced

Identify the error in this Morris traversal snippet

What error will this Rust code cause during Morris inorder traversal?

Code snippet:
let mut pre = node.left.as_mut().unwrap();
while pre.right.is_some() && pre.right.as_ref().unwrap().val != node.val {
pre = pre.right.as_mut().unwrap();
}
if pre.right.is_none() {
pre.right = Some(Box::new(Node { val: node.val, left: None, right: None }));
current = node.left.as_mut();
} else {
pre.right = None;
current = node.right.as_mut();
}

A Runtime error due to infinite loop when pre.right points to node itself.

B Syntax error because of missing semicolons.

C No error; code runs correctly.

D Compile error due to mismatched types in assignment.

💡 Hint

Consider what happens if the thread is not removed properly.

If the thread points back to the node and is not removed, the loop repeats infinitely causing runtime hang.

🚀 Application

advanced

Morris Traversal on a skewed tree

Given a right-skewed binary tree with nodes 1 -> 2 -> 3 -> 4 (each node has only right child), what is the output of Morris inorder traversal?

A [2, 1, 4, 3]

B [1, 2, 3, 4]

C [1, 3, 2, 4]

D [4, 3, 2, 1]

💡 Hint

Inorder traversal visits left subtree, node, then right subtree. Here left subtree is always empty.

Since all nodes only have right children, inorder traversal visits nodes in ascending order: 1, 2, 3, 4.

❓ Predict Output

expert

Output of Morris Traversal on complex tree with duplicates

What is the output of Morris inorder traversal on this tree?

Tree structure:
4
/ \
2 5
/ \ \
2 3 5

Assume traversal prints node values in order.

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn morris_inorder(root: &mut Option<Box<Node>>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut current = root.as_mut().map(|b| &mut **b);
    while let Some(node) = current {
        if node.left.is_none() {
            result.push(node.val);
            current = node.right.as_mut().map(|b| &mut **b);
        } else {
            let mut pre = node.left.as_mut().map(|b| &mut **b).unwrap();
            while pre.right.is_some() && pre.right.as_ref().unwrap().val != node.val {
                pre = pre.right.as_mut().map(|b| &mut **b).unwrap();
            }
            if pre.right.is_none() {
                pre.right = Some(Box::new(Node { val: node.val, left: None, right: None }));
                current = node.left.as_mut().map(|b| &mut **b);
            } else {
                pre.right = None;
                result.push(node.val);
                current = node.right.as_mut().map(|b| &mut **b);
            }
        }
    }
    result
}

fn main() {
    let mut root = Some(Box::new(Node {
        val: 4,
        left: Some(Box::new(Node {
            val: 2,
            left: Some(Box::new(Node { val: 2, left: None, right: None })),
            right: Some(Box::new(Node { val: 3, left: None, right: None })),
        })),
        right: Some(Box::new(Node {
            val: 5,
            left: None,
            right: Some(Box::new(Node { val: 5, left: None, right: None })),
        })),
    }));
    let output = morris_inorder(&mut root);
    println!("{:?}", output);
}

A [2, 2, 3, 4, 5, 5]

B [2, 3, 2, 4, 5, 5]

C [4, 2, 2, 3, 5, 5]

D [2, 2, 3, 5, 5, 4]

💡 Hint

Inorder traversal visits left subtree, node, then right subtree, including duplicates in order.

The traversal visits left subtree nodes 2, 2, 3, then root 4, then right subtree 5, 5 in order.

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