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

Traverse the tree without stack or recursion by creating temporary threads to predecessors, printing nodes in inorder.

Execution Sample

DSA C++

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

void morrisInorder(Node* root) {
  Node* current = root;
  while (current != NULL) {
    if (current->left == NULL) {
      std::cout << current->data << " ";
      current = current->right;
    } else {
      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;
        std::cout << current->data << " ";
        current = current->right;
      }
    }
  }
}

This code prints the inorder traversal of a binary tree without using stack or recursion by temporarily modifying the tree.

Execution Table

Step	Operation	Current Node	Predecessor Node	Thread Created/Removed	Printed Node	Visual State
1	Start at root	1	NULL	None	None	1 / \ 2 3
2	current->left != NULL, find predecessor	1	2	None	None	1 / \ 2 3
3	predecessor->right == NULL, create thread	1	2	Thread 2->right = 1	None	1 / \ 2->1 3 (thread from 2 to 1)
4	Move current to left child	2	NULL	None	None	1 / \ 2->1 3 (thread)
5	current->left == NULL, print current	2	NULL	None	2	1 / \ 2->1 3 (thread)
6	Move current to right child (thread)	1	2	None	None	1 / \ 2->1 3 (thread)
7	current->left != NULL, find predecessor	1	2	None	None	1 / \ 2->1 3 (thread)
8	predecessor->right == current, remove thread	1	2	Remove thread 2->right	None	1 / \ 2 3
9	Print current node	1	NULL	None	1	1 / \ 2 3
10	Move current to right child	3	NULL	None	None	1 / \ 2 3
11	current->left == NULL, print current	3	NULL	None	3	1 / \ 2 3
12	Move current to right child (NULL)	NULL	NULL	None	None	Traversal complete
13	Exit	NULL	NULL	None	None	Traversal complete

💡 current becomes NULL, traversal ends

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 8	After Step 9	After Step 10	After Step 11	Final
current	1	1	2	2	1	1	1	3	3	NULL
predecessor	NULL	2	NULL	NULL	NULL	2	NULL	NULL	NULL	NULL
thread	None	Created 2->right=1	None	None	None	Removed 2->right	None	None	None	None
printed	None	None	None	2	None	None	1	None	3	None

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. See Step 3 where thread 2->right=1 is created.

Why do we remove the thread after visiting the left subtree?

Removing the thread restores the original tree structure and prevents infinite loops. This happens at Step 8 where thread 2->right is removed.

Why do we print the node only when current.left is NULL or after removing the thread?

Printing at these points ensures inorder sequence: left subtree first, then node, then right subtree. See Steps 5, 9, and 11 for printing moments.

Visual Quiz - 3 Questions

Look at the execution table at Step 5, which node is printed?

A Node 1

B Node 2

C Node 3

D No node printed

💡 Hint

Check the 'Printed Node' column at Step 5 in the execution_table.

At which step is the thread from node 2 to node 1 removed?

A Step 3

B Step 6

C Step 8

D Step 10

💡 Hint

Look at the 'Thread Created/Removed' column for removal events.

If the tree had no left children, how would the printed nodes appear in the execution table?

A Printed nodes only when threads are removed

B Printed nodes immediately and no threads created

C No nodes printed

D Threads created but no nodes printed

💡 Hint

Refer to the logic when current->left == NULL in the code and execution_table Steps 5 and 11.

Concept Snapshot

Morris Traversal Inorder Without Stack:
- Uses threaded binary tree concept
- For each node, find predecessor in left subtree
- Create thread from predecessor.right to current if NULL
- If thread exists, remove it and print current
- If no left child, print current and move right
- Traverses inorder without extra space

Full Transcript

Morris Traversal is a way to do inorder traversal of a binary tree without using stack or recursion. It works by temporarily changing the tree structure. Starting at the root, if the current node has no left child, we print it and move to the right child. If it has a left child, we find its inorder 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, print the current node, and move to the right child. This process repeats until current becomes NULL, completing the traversal. This method uses O(1) extra space and restores the tree after traversal.