Morris Traversal Inorder Without Stack in DSA C#

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 know where to come back without carrying a map or notes.

    4
   / \
  2   5
 / \
1   3

Pointers:
curr ↑ at root 4
null means no child

Dry Run Walkthrough

Input: Binary tree: 4 -> 2,5 -> 1,3 (Inorder traversal expected: 1 2 3 4 5)

Goal: Print nodes in inorder without using stack or recursion by modifying tree links temporarily

Step 1: curr at 4, left child exists, find predecessor (rightmost in left subtree)

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

Why: We need to find where to return after finishing left subtree

Step 2: Make 3's right point to curr (4) to remember return path, move curr to left child (2)

4 ← 3 -> 4 [curr]
2 [curr] -> 1 -> 3 -> 4
Temporary link created

Why: Temporary link helps us come back to 4 after left subtree

Step 3: curr at 2, left child exists, find predecessor (1)

2 [curr] -> 1 -> null
Predecessor of 2 is 1

Why: Find return point after left subtree of 2

Step 4: Make 1's right point to curr (2), move curr to left child (1)

1 [curr] -> null
1 -> 2 [curr]
Temporary link created

Why: Remember to return to 2 after left subtree

Step 5: curr at 1, no left child, print 1, move curr to right (which points to 2)

1 printed
curr moves to 2 [curr]

Why: No left subtree, so print and move right

Step 6: curr at 2, predecessor's right points to curr, remove temporary link, print 2, move curr to right (3)

2 printed
Temporary link removed
curr moves to 3 [curr]

Why: Left subtree done, print node and move right

Step 7: curr at 3, no left child, print 3, move curr to right (which points to 4)

3 printed
curr moves to 4 [curr]

Why: No left subtree, print and move right

Step 8: curr at 4, predecessor's right points to curr, remove temporary link, print 4, move curr to right (5)

4 printed
Temporary link removed
curr moves to 5 [curr]

Why: Left subtree done, print node and move right

Step 9: curr at 5, no left child, print 5, move curr to right (null)

5 printed
curr moves to null (end)

Why: No left subtree, print and finish

Result:

1 -> 2 -> 3 -> 4 -> 5 -> null
Printed inorder traversal without stack or recursion

Annotated Code

DSA C#

using System;

class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

class MorrisTraversal {
    public static void Inorder(Node root) {
        Node curr = root;
        while (curr != null) {
            if (curr.left == null) {
                Console.Write(curr.val + " ");
                curr = curr.right; // move right if no left child
            } else {
                Node pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right; // find rightmost node in left subtree
                }
                if (pred.right == null) {
                    pred.right = curr; // create temporary link to curr
                    curr = curr.left; // move to left child
                } else {
                    pred.right = null; // remove temporary link
                    Console.Write(curr.val + " ");
                    curr = curr.right; // move right after left subtree
                }
            }
        }
    }

    static void Main() {
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(5);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        Inorder(root);
        Console.WriteLine();
    }
}

while (curr != null) {

continue traversal until all nodes are visited

if (curr.left == null) {

if no left child, print and move right

curr = curr.right; // move right if no left child

advance to next node on right

Node pred = curr.left;

find predecessor in left subtree

while (pred.right != null && pred.right != curr) { pred = pred.right; }

find rightmost node in left subtree or temporary link

if (pred.right == null) { pred.right = curr; curr = curr.left; }

create temporary link and move left

else { pred.right = null; Console.Write(curr.val + " "); curr = curr.right; }

remove temporary link, print node, move right

Output

1 2 3 4 5 

Complexity Analysis

Time: O(n) because each edge is visited at most twice during traversal

Space: O(1) because no extra stack or recursion is used, only pointers modified temporarily

vs Alternative: Unlike recursive or stack-based inorder which use O(h) space, Morris traversal uses no extra space but modifies tree temporarily

Edge Cases

Empty tree (root is null)

No output, traversal ends immediately

DSA C#

while (curr != null) {

Tree with single node

Prints the single node value correctly

DSA C#

if (curr.left == null) {

Tree with only right children

Traversal prints nodes in order without creating temporary links

DSA C#

if (curr.left == null) {

When to Use This Pattern

When asked to do inorder traversal without recursion or stack, think of Morris traversal which uses temporary tree links to remember return paths.

Common Mistakes

Mistake: Not restoring the tree by removing temporary links after visiting left subtree
Fix: Always remove the temporary link (pred.right = null) before moving right

Mistake: Incorrectly finding predecessor by not checking if pred.right == curr
Fix: Check pred.right != curr to avoid infinite loops and detect temporary links

Summary

Prints inorder traversal of a binary tree without using stack or recursion by temporarily modifying tree links.

Use when you want inorder traversal with O(1) extra space and can modify the tree temporarily.

The key insight is to create and remove temporary right links from the inorder predecessor to the current node to remember return paths.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to the traditional recursive or stack-based methods?

easy

A. It works only on binary search trees.

B. It is faster than all other traversal methods.

C. It uses no extra space for stack or recursion.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal uses threaded binary trees to avoid recursion or stack, so it uses O(1) extra space.

2. Step 2: Compare with other methods

   Recursive and stack-based traversals use O(h) space where h is tree height, so Morris Traversal saves memory.

3. Final Answer:

   It uses no extra space for stack or recursion. -> Option C

4. Quick Check:

   Space complexity = O(1) [OK]

Hint: Morris Traversal uses threading to avoid extra space [OK]

Common Mistakes:

• Thinking it is faster than recursive traversal
• Assuming it only works on BSTs
• Believing it permanently changes the tree

2. Which of the following C# code snippets correctly initializes the current node for Morris inorder traversal?

easy

A. TreeNode current = root;

B. TreeNode current = null;

C. TreeNode current = root.left;

D. TreeNode current = root.right;

Solution

1. Step 1: Identify starting point for traversal

   Morris traversal starts from the root node to cover the entire tree.

2. Step 2: Check initialization correctness

   Initializing current as root ensures traversal begins at the tree's root.

3. Final Answer:

   TreeNode current = root; -> Option A

4. Quick Check:

   Start traversal at root node [OK]

Hint: Start traversal from root node always [OK]

Common Mistakes:

• Starting from null causes no traversal
• Starting from left or right child misses nodes

3. What will be the output of the Morris inorder traversal on the following binary tree?

    2
   / \
  1   3

Assuming the traversal prints node values separated by spaces.

medium

A. 3 2 1

B. 1 2 3

C. 2 1 3

D. 1 3 2

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, root, then right subtree.

2. Step 2: Apply Morris traversal order on given tree

   Left child 1, then root 2, then right child 3 results in "1 2 3".

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Inorder = left-root-right = 1 2 3 [OK]

Hint: Inorder = left, root, right [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Misreading tree structure

4. Consider this snippet of Morris inorder traversal code in C#:

while (current != null) {
    if (current.left == null) {
        Console.Write(current.val + " ");
        current = current.right;
    } else {
        TreeNode predecessor = current.left;
        while (predecessor.right != null && predecessor.right == current) {
            predecessor = predecessor.right;
        }
        if (predecessor.right == null) {
            predecessor.right = current;
            current = current.left;
        } else {
            predecessor.right = null;
            Console.Write(current.val + " ");
            current = current.right;
        }
    }
}

What is the bug in this code?

medium

A. The code does not handle the case when current.left is null.

B. The Console.Write statements should be outside the if-else blocks.

C. The predecessor.right pointer is never reset to null, causing infinite loop.

D. The inner while loop should check predecessor.right != current instead of predecessor.right == current.

Solution

1. Step 1: Analyze inner while loop condition

   The loop should continue while predecessor.right != null && predecessor.right != current to reach the rightmost node in left subtree.

2. Step 2: Check given condition correctness

   The code uses predecessor.right == current, which fails to traverse the right chain properly, as it only continues if already threaded back.

3. Step 3: Why other options are wrong

   A: left null is handled in if. C: reset happens in else. D: print placement is correct for inorder.

4. Final Answer:

   The inner while loop should check predecessor.right != current instead of predecessor.right == current. -> Option D

5. Quick Check:

   Loop condition must be != null && != current [OK]

Hint: Check loop conditions carefully to avoid infinite loops [OK]

Common Mistakes:

• Confusing loop condition signs
• Forgetting to reset threaded pointers
• Misplacing print statements

5. You want to modify Morris inorder traversal to count the number of nodes in a binary tree without using extra space or recursion. Which modification is correct?

hard

A. Increment a counter each time you print a node's value during traversal.

B. Increment a counter only when you create a threaded link.

C. Increment a counter only when you remove a threaded link.

D. Increment a counter only when current.left is null.

Solution

1. Step 1: Identify when nodes are visited in Morris traversal

   Nodes are visited (printed) when current.left is null or after removing threaded link.

2. Step 2: Counting nodes correctly

   Incrementing counter when printing nodes ensures counting all nodes exactly once.

3. Step 3: Why other options fail

   Incrementing only on creating or removing threaded links misses nodes or counts duplicates.

4. Final Answer:

   Increment a counter each time you print a node's value during traversal. -> Option A

5. Quick Check:

   Count nodes when visiting them [OK]

Hint: Count nodes when printing during traversal [OK]

Common Mistakes:

• Counting on threaded link creation/removal
• Counting only left-null nodes
• Missing some nodes in count