Morris Traversal Inorder Without Stack in DSA Rust

Mental Model

We visit nodes in order without using extra memory by temporarily changing tree links to remember where to return.

Analogy: Imagine walking through a maze and leaving temporary signs on walls to find your way back without carrying a map or breadcrumbs.

    4
   / \
  2   5
 / \
1   3

↑ root points to 4

Dry Run Walkthrough

Input: Binary tree: 4 -> 2 -> 1, 3 and 4 -> 5; perform inorder traversal using Morris Traversal

Goal: Print nodes in inorder sequence: 1 -> 2 -> 3 -> 4 -> 5 without using stack or recursion

Step 1: Start at root (4), find predecessor of 4 in left subtree (rightmost node of 2's subtree)

4 [curr] -> 2 -> 1 -> 3 -> 5
Predecessor of 4 is 3

Why: We need to link predecessor's right to current to return after left subtree

Step 2: Set 3's right pointer to 4 (thread), move curr to left child 2

4
 ↑
2 [curr] -> 1 -> 3 -> (3.right -> 4)
5
Thread created from 3 to 4

Why: Thread allows returning to 4 after finishing left subtree

Step 3: At 2, find predecessor in left subtree (1), set 1's right to 2, move curr to 1

2
 ↑
1 [curr] -> (1.right -> 2)
3 -> (3.right -> 4)
5

Why: Thread from 1 to 2 to return after left subtree of 2

Step 4: At 1, no left child, print 1, move curr to right (which is thread to 2)

Print: 1
Curr moves to 2 via thread
2 [curr] -> 3 -> (3.right -> 4)
5

Why: No left subtree, so print and follow thread back

Step 5: At 2, thread from 1 detected, remove thread, print 2, move curr to right child 3

Print: 2
Thread removed (1.right = None)
Curr moves to 3
3 [curr] -> (3.right -> 4)
5

Why: Left subtree done, print node and move right

Step 6: At 3, no left child, print 3, move curr to right (thread to 4)

Print: 3
Curr moves to 4 via thread
4 [curr] -> 5
Thread from 3 to 4 still exists

Why: No left subtree, print and follow thread

Step 7: At 4, thread from 3 detected, remove thread, print 4, move curr to right child 5

Print: 4
Thread removed (3.right = None)
Curr moves to 5
5 [curr]

Why: Left subtree done, print node and move right

Step 8: At 5, no left child, print 5, move curr to right null, traversal ends

Print: 5
Curr moves to None
Traversal complete

Why: No more nodes to visit

Result:

1 -> 2 -> 3 -> 4 -> 5 -> null

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn morris_inorder(root: Option<Rc<RefCell<TreeNode>>>) {
    let mut curr = root;
    while let Some(node_rc) = curr.clone() {
        let mut node = node_rc.borrow_mut();
        if node.left.is_none() {
            // No left child, print and move right
            print!("{} -> ", node.val);
            curr = node.right.clone();
        } else {
            // Find predecessor
            let mut pred = node.left.clone();
            while let Some(pred_rc) = pred.clone() {
                let pred_node = pred_rc.borrow();
                if pred_node.right.is_some() && pred_node.right.as_ref().unwrap().as_ptr() == node_rc.as_ptr() {
                    break;
                }
                if pred_node.right.is_none() {
                    break;
                }
                pred = pred_node.right.clone();
            }

            if let Some(pred_rc) = pred {
                let mut pred_node = pred_rc.borrow_mut();
                if pred_node.right.is_none() {
                    // Create thread
                    pred_node.right = Some(node_rc.clone());
                    curr = node.left.clone();
                } else {
                    // Thread exists, remove it
                    pred_node.right = None;
                    print!("{} -> ", node.val);
                    curr = node.right.clone();
                }
            }
        }
    }
    print!("null\n");
}

fn main() {
    // Build tree:
    //     4
    //    / \
    //   2   5
    //  / \
    // 1   3
    let n1 = TreeNode::new(1);
    let n3 = TreeNode::new(3);
    let n2 = TreeNode::new(2);
    n2.borrow_mut().left = Some(n1);
    n2.borrow_mut().right = Some(n3);
    let n5 = TreeNode::new(5);
    let n4 = TreeNode::new(4);
    n4.borrow_mut().left = Some(n2);
    n4.borrow_mut().right = Some(n5);

    morris_inorder(Some(n4));
}

while let Some(node_rc) = curr.clone() {

loop until all nodes visited

if node.left.is_none() {

if no left child, print and move right

print!("{} -> ", node.val);

print current node value

curr = node.right.clone();

move to right child

let mut pred = node.left.clone();

find predecessor in left subtree

while let Some(pred_rc) = pred.clone() { ... }

move to rightmost node in left subtree or detect thread

if pred_node.right.is_none() { pred_node.right = Some(node_rc.clone()); curr = node.left.clone(); }

create thread and move left

else { pred_node.right = None; print!("{} -> ", node.val); curr = node.right.clone(); }

remove thread, print node, move right

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because each edge is visited at most twice during threading and removal

Space: O(1) because no extra stack or recursion is used, only temporary threads

vs Alternative: Compared to recursion or stack-based inorder traversal which use O(h) space, Morris traversal uses constant space by modifying tree temporarily

Edge Cases

Empty tree

No output, traversal ends immediately

DSA Rust

while let Some(node_rc) = curr.clone() {

Single node tree

Print single node value and null

DSA Rust

if node.left.is_none() {

Tree with no left children

Print nodes in order by moving right only

DSA Rust

if node.left.is_none() {

When to Use This Pattern

When asked to do inorder traversal without extra memory like stack or recursion, use Morris Traversal to temporarily link nodes and achieve O(1) space.

Common Mistakes

Mistake: Not restoring the tree by removing threads after visiting left subtree
Fix: Remove the temporary thread by setting predecessor's right pointer back to None after returning

Mistake: Confusing predecessor detection and creating infinite loops
Fix: Carefully check if predecessor's right points to current node before creating or removing thread

Summary

Morris Traversal prints inorder nodes without stack or recursion by temporarily linking nodes.

Use it when you want inorder traversal with O(1) extra space.

The key insight is to create and remove temporary threads to remember where to return after left subtree.

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