Morris Traversal Inorder Without Stack in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to move to the left child in Morris traversal.

DSA Rust

while current.is_some() {
    let mut node = current.unwrap();
    if node.left.is_none() {
        print!("{} ", node.val);
        current = node.[1];
    } else {
        // Find predecessor
    }
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Moving to left child instead of right when left is None.

Trying to access parent pointer which may not exist.

In Morris traversal, when left child is None, we print current node and move to its right child.

2fill in blank

medium

Complete the code to find the inorder predecessor in Morris traversal.

DSA Rust

let mut predecessor = node.left.as_ref().unwrap();
while predecessor.right.is_some() && predecessor.right.as_ref() != Some(&node) {
    predecessor = predecessor.[1].as_ref().unwrap();
}

Drag options to blanks, or click blank then click option'

Aleft

Bparent

Cright

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Moving to left child instead of right child to find predecessor.

Not checking if predecessor's right points back to current node.

The inorder predecessor is found by moving to the rightmost node in left subtree.

3fill in blank

hard

Fix the error in setting the temporary link from predecessor to current node.

DSA Rust

if predecessor.right.is_none() {
    predecessor.right = Some(Box::new(node.[1]));
    current = node.left.clone();
}

Drag options to blanks, or click blank then click option'

Aas_ref()

Bval

Cright

Dclone()

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning a clone of left child instead of current node.

Using val instead of node reference.

We must set predecessor.right to point to current node itself, not a clone of its child.

4fill in blank

hard

Fill both blanks to remove the temporary link and move to the right child.

DSA Rust

else {
    predecessor.right = [1];
    print!("{} ", node.val);
    current = node.[2].clone();
}

Drag options to blanks, or click blank then click option'

ANone

BSome(Box::new(node))

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Setting predecessor.right to Some instead of None.

Moving to left child instead of right child after removal.

We remove the temporary link by setting predecessor.right to None and move to current's right child.

5fill in blank

hard

Fill all three blanks to complete the Morris inorder traversal loop.

DSA Rust

while let Some(node) = current.clone() {
    if node.left.is_none() {
        print!("{} ", node.val);
        current = node.[1].clone();
    } else {
        let mut predecessor = node.left.as_ref().unwrap();
        while predecessor.right.is_some() && predecessor.right.as_ref() != Some(&node) {
            predecessor = predecessor.[2].as_ref().unwrap();
        }
        if predecessor.right.is_none() {
            predecessor.right = Some(Box::new(node.clone()));
            current = node.[3].clone();
        } else {
            predecessor.right = None;
            print!("{} ", node.val);
            current = node.right.clone();
        }
    }
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cclone()

Dval

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing left and right pointers in traversal.

Not cloning nodes properly causing ownership errors.

Move to right child when no left child; find predecessor by moving right; set current to left child after linking.

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