Morris Traversal Inorder Without Stack in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Morris Traversal for inorder tree traversal?

Morris Traversal uses threaded binary trees by temporarily modifying the tree's right pointers to avoid using a stack or recursion, enabling inorder traversal with O(1) extra space.

intermediate

In Morris Traversal, what do we do when the current node has a left child?

We find the rightmost node in the left subtree (predecessor). If its right pointer is null, we set it to the current node (threading) and move current to its left child. If the right pointer points back to current, we revert it to null and visit current.

beginner

Why does Morris Traversal not require a stack or recursion?

Because it temporarily creates threads (links) to predecessor nodes, allowing the traversal to return to parent nodes without extra memory, thus achieving O(1) space complexity.

intermediate

What happens to the tree structure after Morris Traversal completes?

All temporary threads (right pointers) created during traversal are reverted back to null, restoring the original tree structure exactly as it was before traversal.

advanced

Show the Rust code snippet to find the inorder predecessor in Morris Traversal.

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

What is the space complexity of Morris Traversal for inorder traversal?

A O(n)

B O(1)

C O(log n)

D O(n log n)

Morris Traversal uses threading to avoid stack or recursion, so it uses constant extra space O(1).

In Morris Traversal, what does the 'thread' refer to?

A A left pointer from current to predecessor

B A recursive call

C A stack frame storing nodes

D A temporary right pointer from predecessor to current node

The thread is a temporary right pointer from the inorder predecessor back to the current node.

When do we visit (print) the current node in Morris Traversal?

A Only after visiting right subtree

B Only when current has a left child

C When current has no left child or after restoring the thread

D Before creating any thread

We visit current when it has no left child or after we revert the thread from predecessor to current.

What happens if we forget to revert the thread in Morris Traversal?

A The tree structure is permanently changed

B Traversal will fail to visit all nodes

C Traversal will use extra stack space

D Traversal will become recursive

Not reverting threads leaves the tree modified, which is undesirable.

Which traversal order does Morris Traversal implement in this context?

A Inorder

B Preorder

C Postorder

D Level order

This Morris Traversal implementation is for inorder traversal.

Explain step-by-step how Morris Traversal performs inorder traversal without using a stack or recursion.

Think about how the traversal moves left, visits, and then moves right using temporary links.

Describe how Morris Traversal restores the original tree structure after traversal.

Focus on what happens when the traversal returns to a node via a thread.

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