Morris Traversal Inorder Without Stack in DSA C# - Execution Trace

Concept Flow - Morris Traversal Inorder Without Stack

Start at root

↓

Check if current.left is null?

Yes→Visit current node

↓

Move to current.right

↓

Find predecessor in left subtree

↓

Check if predecessor.right is null?

Yes→Make thread: predecessor.right = current

↓

Remove thread: predecessor.right = null

↓

Move current to current.left

↓

Move current to current.right

↓

Repeat until current is null

Traverse the tree without stack by creating temporary threads to predecessors, visiting nodes in inorder sequence.

Execution Sample

DSA C#

TreeNode current = root;
while (current != null) {
  if (current.left == null) {
    Visit(current);
    current = current.right;
  } else {
    TreeNode pred = current.left;
    // Find predecessor
  }
}

Traverse binary tree inorder without stack by threading predecessors and visiting nodes.

Execution Table

Step	Operation	Current Node	Predecessor Node	Thread Created/Removed	Visual State (Inorder Visited)
1	Start at root	1	null	None	[]
2	current.left != null, find predecessor	1	5	None	[]
3	predecessor.right == null, create thread	1	5	Thread 5.right -> 1	[]
4	Move current to current.left	5	null	None	[]
5	current.left != null, find predecessor	5	2	None	[]
6	predecessor.right == null, create thread	5	2	Thread 2.right -> 5	[]
7	Move current to current.left	2	null	None	[]
8	current.left == null, visit node	2	null	None	[2]
9	Move current to current.right	2	null	None	[2]
10	current == 5 (via thread), predecessor.right == current, remove thread	5	2	Remove thread 2.right	[2]
11	Visit current node	5	null	None	[2, 5]
12	Move current to current.right	5	null	None	[2, 5]
13	current == 1, current.left != null, find predecessor	1	5	None	[2, 5]
14	predecessor.right == current, remove thread	1	5	Remove thread 5.right	[2, 5]
15	Visit current node	1	null	None	[2, 5, 1]
16	Move current to current.right	1	null	None	[2, 5, 1]
17	current == 3, current.left != null, find predecessor	3	6	None	[2, 5, 1]
18	predecessor.right == null, create thread	3	6	Thread 6.right -> 3	[2, 5, 1]
19	Move current to current.left	6	null	None	[2, 5, 1]
20	current.left == null, visit node	6	null	None	[2, 5, 1, 6]
21	Move current to current.right	6	null	None	[2, 5, 1, 6]
22	current == 3 (via thread), predecessor.right == current, remove thread	3	6	Remove thread 6.right	[2, 5, 1, 6]
23	Visit current node	3	null	None	[2, 5, 1, 6, 3]
24	Move current to current.right	3	null	None	[2, 5, 1, 6, 3]
25	current == null, traversal ends	null	null	None	[2, 5, 1, 6, 3]

💡 current becomes null, traversal finished with inorder visited nodes [2, 5, 1, 6, 3]

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 10	After Step 14	After Step 18	After Step 22	Final
current	1	5	2	5	1	3	3	null
predecessor	null	5	2	2	5	6	6	null
Thread Created/Removed	None	Thread 5.right->1	Thread 2.right->5	Remove thread 2.right	Remove thread 5.right	Thread 6.right->3	Remove thread 6.right	None
Inorder Visited	[]	[]	[2]	[2]	[2, 5, 1]	[2, 5, 1]	[2, 5, 1, 6, 3]	[2, 5, 1, 6, 3]

Key Moments - 3 Insights

Why do we create a thread from predecessor.right to current?

Creating the thread allows us to return to the current node after finishing the left subtree without using a stack, as shown in steps 3 and 6 where threads are created.

Why do we remove the thread when predecessor.right points back to current?

Removing the thread restores the original tree structure and signals that the left subtree has been fully visited, as seen in steps 10, 14, and 22.

Why do we visit the current node only when current.left is null or after removing a thread?

Visiting at these points ensures inorder sequence: left subtree first, then node, then right subtree. This is clear in steps 8, 11, 13, 15, 20, and 23.

Visual Quiz - 3 Questions

Look at the execution table, at which step is the first thread created?

A Step 3

B Step 6

C Step 10

D Step 15

💡 Hint

Check the 'Thread Created/Removed' column in the execution table rows.

At which step does the traversal visit node 5?

A Step 13

B Step 8

C Step 11

D Step 21

💡 Hint

Look at the 'Operation' and 'Visual State' columns to find when node 5 is added.

If we skip removing the thread at step 10, what happens next?

A Traversal visits node 2 twice

B Traversal gets stuck in an infinite loop

C Traversal skips node 4

D Traversal ends early

💡 Hint

Consider how the thread controls moving back to current node without stack.

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Uses threaded binary tree to avoid stack/recursion
- For each node, find predecessor in left subtree
- Create thread from predecessor.right to current if null
- Visit node when left is null or after removing thread
- Move current accordingly until null
- Restores tree by removing threads after use

Full Transcript

Morris Traversal is a way to do inorder traversal of a binary tree without using extra space like stack or recursion. It works by temporarily changing the tree structure to create threads from a node's inorder predecessor back to the node. We start at the root and for each node, if it has no left child, we visit it and move to the right child. If it has a left child, we find its predecessor in the left subtree. If the predecessor's right pointer is null, we create a thread to the current node and move current to its left child. If the thread already exists, we remove it, visit the current node, and move to the right child. This process continues until current becomes null, visiting nodes in inorder sequence and restoring the original tree structure. The execution table shows each step, the current node, predecessor, thread creation/removal, and the visited nodes so far. Key moments include why threads are created and removed, and when nodes are visited to maintain inorder order. The variable tracker shows how current, predecessor, threads, and visited nodes change step by step. This method is efficient and uses O(1) space by cleverly using the tree's own pointers.

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