Morris Traversal Inorder Without Stack in DSA Rust - Time & Space Complexity

Time Complexity: Morris Traversal Inorder Without Stack

O(n)

Understanding Time Complexity

We want to understand how the Morris Traversal algorithm performs as the tree size grows.

Specifically, how many steps it takes to visit all nodes without using extra memory for a stack.

Scenario Under Consideration

Analyze the time complexity of the following Morris Inorder Traversal code.

fn morris_inorder(root: Option<&Box>) {
    let mut current = root;
    while let Some(node) = current {
        if node.left.is_none() {
            // Visit node
            current = node.right.as_ref();
        } else {
            let mut pre = node.left.as_ref();
            while pre.unwrap().right.is_some() && pre.unwrap().right.as_ref() != current {
                pre = pre.unwrap().right.as_ref();
            }
            if pre.unwrap().right.is_none() {
                // Unsafe block needed to modify right pointer
                // This code is conceptual; actual Rust code requires mutable references
                // pre.unwrap().right = current;
                current = node.left.as_ref();
            } else {
                // pre.unwrap().right = None;
                // Visit node
                current = node.right.as_ref();
            }
        }
    }
}
    

This code visits all nodes of a binary tree in order without using a stack or recursion by temporarily modifying tree links.

Identify Repeating Operations

Look for loops and repeated steps in the code.

• Primary operation: The inner while loop that finds the rightmost node in the left subtree (predecessor).
• How many times: Each edge in the tree is visited at most twice during these pointer changes.

How Execution Grows With Input

As the number of nodes (n) increases, the algorithm visits each node and its edges a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 visits (nodes and edges)
100	About 200 visits
1000	About 2000 visits

Pattern observation: The operations grow roughly linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the algorithm visits each node a constant number of times, so the total steps grow directly with tree size.

Common Mistake

[X] Wrong: "Because of the inner loop, Morris traversal is slower than normal inorder traversal and can be O(n²)."

[OK] Correct: Each edge is visited at most twice, so the total work is still proportional to n, not n squared.

Interview Connect

Understanding Morris traversal shows you can save memory by clever pointer use, a skill valued in interviews and real coding.

Self-Check

"What if we changed the tree to be a linked list (all nodes have only right child)? How would the time complexity change?"

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