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→Print current.data

↓

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

↓

Repeat until current is NULL

This flow shows how Morris Traversal uses temporary threads to traverse the tree inorder without stack or recursion.

Execution Sample

DSA C

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

void morrisInorder(struct Node* root) {
  struct Node* current = root;
  while (current != NULL) {
    if (current->left == NULL) {
      printf("%d ", current->data);
      current = current->right;
    } else {
      struct Node* 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;
        printf("%d ", current->data);
        current = current->right;
      }
    }
  }
}

This code performs inorder traversal of a binary tree without using stack or recursion by creating temporary threads.

Execution Table

Step	Operation	Current Node	Predecessor	Thread Created/Removed	Printed Node	Visual Tree State
1	Start at root	1	N/A	No	No	1 / \ 2 3
2	current->left != NULL, find predecessor	1	2	No	No	1 / \ 2 3
3	predecessor->right == NULL, create thread	1	2	Thread created: 2->right = 1	No	1 / \ 2->1 3
4	Move current to left child	2	N/A	No	No	1 / \ 2->1 3
5	current->left == NULL, print current	2	N/A	No	2	1 / \ 2->1 3
6	Move current to right (thread back to 1)	1	2	No	No	1 / \ 2->1 3
7	predecessor->right == current, remove thread	1	2	Thread removed: 2->right = NULL	No	1 / \ 2 3
8	Print current node	1	N/A	No	1	1 / \ 2 3
9	Move current to right child	3	N/A	No	No	1 / \ 2 3
10	current->left == NULL, print current	3	N/A	No	3	1 / \ 2 3
11	Move current to right (NULL)	NULL	N/A	No	No	1 / \ 2 3
12	Traversal ends	NULL	N/A	No	No	1 / \ 2 3

💡 current becomes NULL, traversal ends

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 7	After Step 9	Final
current	1	1	2	1	1	3	NULL
predecessor	N/A	2	N/A	2	2	N/A	N/A
thread (predecessor->right)	NULL	1 (created)	1 (threaded)	1 (threaded)	NULL (removed)	NULL	NULL

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 execution_table step 3.

Why do we remove the thread later?

Removing the thread restores the original tree structure after visiting the left subtree, as seen in execution_table step 7.

What happens when current->left is NULL?

We print the current node and move to its right child directly, as in steps 5 and 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what node is printed?

A Node 1

B Node 3

C Node 2

D No node printed

💡 Hint

Check the 'Printed Node' column at step 5 in execution_table

At which step is the thread from predecessor.right removed?

A Step 3

B Step 7

C Step 6

D Step 9

💡 Hint

Look at the 'Thread Created/Removed' column in execution_table

If the tree had no left children, how would the traversal change?

A Nodes would be printed immediately and traversal moves right

B Threads would still be created

C Traversal would not print any nodes

D Traversal would get stuck in a loop

💡 Hint

Refer to the condition when current->left == NULL in execution_table steps 5 and 10

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Uses temporary threads to traverse without recursion or stack
- For each node, find predecessor in left subtree
- Create thread from predecessor.right to current if none exists
- If thread exists, remove it and print current
- If no left child, print current and move right
- Restores tree structure after traversal

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 creating temporary threads from a node's inorder predecessor back to the node. When we reach a node with no left child, we print it and move right. If a left child exists, we find its predecessor. If the predecessor's right pointer is NULL, we create a thread to the current node and move left. If the thread already exists, we remove it, print the current node, and move right. This way, we visit nodes in inorder sequence and restore the tree after traversal.

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to traditional methods?

easy

A. It only works on binary search trees

B. It is faster than all other traversal methods

C. It uses no extra space like stack or recursion

D. It requires a special tree structure

Solution

1. Step 1: Understand traditional inorder traversal space usage

   Traditional inorder traversal uses recursion or a stack, which requires extra memory proportional to tree height.

2. Step 2: Identify Morris Traversal space usage

   Morris Traversal modifies tree links temporarily to avoid stack or recursion, using O(1) extra space.

3. Final Answer:

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

4. Quick Check:

   Morris Traversal = O(1) space [OK]

Hint: Morris uses tree links, no stack or recursion needed [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Assuming it only works on BSTs
• Believing it needs special tree nodes

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

easy

A. struct Node* current = root;

B. struct Node current = root;

C. Node* current = NULL;

D. struct Node* current = NULL;

Solution

1. Step 1: Understand pointer initialization in C for tree traversal

   We need a pointer to the root node to start traversal, so 'struct Node* current = root;' is correct.

2. Step 2: Check other options for correctness

   struct Node current = root; declares a struct variable, not a pointer, which is incorrect. Node* current = NULL; uses 'Node*' without 'struct' keyword, invalid in C. struct Node* current = NULL; initializes current to NULL, which won't start traversal.

3. Final Answer:

   struct Node* current = root; -> Option A

4. Quick Check:

   Pointer to root = struct Node* current = root; [OK]

Hint: Use pointer to root node: struct Node* current = root; [OK]

Common Mistakes:

• Using struct variable instead of pointer
• Omitting 'struct' keyword in C
• Initializing current to NULL instead of root

3. What is 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. 1 3 2

B. 1 2 3

C. 3 2 1

D. 2 1 3

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then root, then right subtree. For this tree, left is 1, root is 2, right is 3.

2. Step 2: Apply Morris traversal logic

   Morris traversal visits nodes in inorder without stack. The output will be "1 2 3 " as it visits left child, root, then right child.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Inorder of tree = 1 2 3 [OK]

Hint: Inorder = left, root, right; output matches this order [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Forgetting spaces in output
• Misreading tree structure

4. Identify the bug in this Morris inorder traversal snippet:

while (current != NULL) {
  if (current->left == NULL) {
    printf("%d ", current->data);
    current = current->right;
  } else {
    struct Node* pre = current->left;
    while (pre->right != NULL) {
      pre = pre->right;
    }
    pre->right = current;
    current = current->left;
  }
}

medium

A. Should use recursion instead of loop

B. Missing initialization of current pointer

C. Incorrect print statement syntax

D. The inner while loop should check pre->right != current

Solution

1. Step 1: Analyze inner while loop condition

   The inner loop finds the rightmost node in left subtree. It should stop if pre->right points back to current to avoid infinite loop.

2. Step 2: Identify correct condition

   The condition must be 'pre->right != NULL && pre->right != current' to detect if thread already exists and avoid infinite loop.

3. Final Answer:

   The inner while loop should check pre->right != current -> Option D

4. Quick Check:

   Loop condition must detect thread to current [OK]

Hint: Check thread link to current in inner loop condition [OK]

Common Mistakes:

• Not checking pre->right != current causes infinite loop
• Forgetting to restore tree links after traversal
• Confusing recursion with Morris traversal

5. Given a binary tree where some nodes have only left children, how does Morris inorder traversal handle these nodes without using stack or recursion?

hard

A. It creates temporary threads from rightmost left child back to current node

B. It skips nodes without right children

C. It uses a stack internally to track nodes

D. It converts the tree into a linked list first

Solution

1. Step 1: Understand Morris traversal threading

   Morris traversal creates temporary links (threads) from the rightmost node of left subtree back to the current node to remember where to return.

2. Step 2: Apply to nodes with only left children

   For nodes with only left children, it finds the rightmost node in left subtree (which may be the left child itself) and creates a thread back to current node, enabling traversal without stack.

3. Final Answer:

   It creates temporary threads from rightmost left child back to current node -> Option A

4. Quick Check:

   Temporary threads enable traversal without stack [OK]

Hint: Threads link back to current node from left subtree's rightmost node [OK]

Common Mistakes:

• Assuming nodes without right children are skipped
• Thinking Morris uses stack internally
• Believing tree is converted to linked list