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.

Practice

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

easy

A. It sorts the tree nodes during traversal

B. It is faster because it uses multiple threads

C. It requires the tree to be a binary search tree

D. It uses no extra space for stack or recursion, only modifies tree temporarily

Solution

1. Step 1: Understand Morris Traversal space usage

   Morris Traversal does not use recursion or an explicit stack, instead it temporarily modifies the tree's right pointers to traverse.

2. Step 2: Compare with traditional methods

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

3. Final Answer:

   It uses no extra space for stack or recursion, only modifies tree temporarily -> Option D

4. Quick Check:

   Space efficiency = No extra stack [OK]

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

Common Mistakes:

• Thinking Morris sorts nodes
• Assuming it needs a binary search tree
• Believing it uses threads or parallelism

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

easy

A. Node current = root;

B. Node* current = root;

C. Node* current = new Node(root);

D. Node current = *root;

Solution

1. Step 1: Understand pointer usage in C++ for tree traversal

   We need a pointer to traverse nodes, so current should be a pointer to Node initialized to root pointer.

2. Step 2: Analyze options

   Node* current = root; correctly declares a pointer and assigns root. Options B and D declare objects, not pointers. Node* current = new Node(root); incorrectly uses new with root pointer.

3. Final Answer:

   Node* current = root; -> Option B

4. Quick Check:

   Pointer initialization = Node* current = root [OK]

Hint: Use pointer Node* current = root for traversal [OK]

Common Mistakes:

• Declaring current as object instead of pointer
• Using new operator incorrectly
• Dereferencing root without pointer

3. Consider the following C++ code snippet implementing Morris inorder traversal on a binary tree with nodes 1, 2, 3 where 1 is root, 2 is left child, and 3 is right child. What is the output printed?

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

void morrisInorder(Node* root) {
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      std::cout << current->data << " ";
      current = current->right;
    } else {
      Node* pre = current->left;
      while (pre->right != nullptr && pre->right != current) {
        pre = pre->right;
      }
      if (pre->right == nullptr) {
        pre->right = current;
        current = current->left;
      } else {
        pre->right = nullptr;
        std::cout << current->data << " ";
        current = current->right;
      }
    }
  }
}

// Tree: 1
//      / \
//     2   3

int main() {
  Node n1{1, nullptr, nullptr};
  Node n2{2, nullptr, nullptr};
  Node n3{3, nullptr, nullptr};
  n1.left = &n2;
  n1.right = &n3;
  morrisInorder(&n1);
  return 0;
}

medium

A. 3 1 2

B. 1 2 3

C. 2 1 3

D. 2 3 1

Solution

1. Step 1: Understand inorder traversal order

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

2. Step 2: Trace Morris traversal output

   Morris traversal prints nodes in inorder without stack. It prints 2 first (left child), then 1 (root), then 3 (right child).

3. Final Answer:

   2 1 3 -> Option C

4. Quick Check:

   Inorder output = 2 1 3 [OK]

Hint: Inorder = left, root, right; output matches 2 1 3 [OK]

Common Mistakes:

• Confusing preorder or postorder output
• Ignoring temporary link restoration
• Assuming output is sorted only for BST

4. The following code attempts Morris inorder traversal but causes an infinite loop. What is the bug?

void morrisInorder(Node* root) {
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      std::cout << current->data << " ";
      current = current->right;
    } else {
      Node* pre = current->left;
      while (pre->right != nullptr) {
        pre = pre->right;
      }
      if (pre->right == nullptr) {
        pre->right = current;
        current = current->left;
      } else {
        pre->right = nullptr;
        std::cout << current->data << " ";
        current = current->right;
      }
    }
  }
}

medium

A. The inner while loop misses checking pre->right != current causing infinite loop

B. The current pointer is not updated after printing

C. The code does not handle nullptr root

D. The pre pointer is not initialized correctly

Solution

1. Step 1: Analyze inner while loop condition

   The inner while loop should check if pre->right is not nullptr and not equal to current to avoid infinite loop.

2. Step 2: Identify missing condition causing infinite loop

   Missing check pre->right != current causes loop to never break when pre->right points back to current, causing infinite loop.

3. Final Answer:

   The inner while loop misses checking pre->right != current causing infinite loop -> Option A

4. Quick Check:

   Loop condition must check pre->right != current [OK]

Hint: Check inner loop condition includes pre->right != current [OK]

Common Mistakes:

• Ignoring second condition in inner loop
• Forgetting to update current after printing
• Not handling empty tree

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?

void morrisCount(Node* root) {
  int count = 0;
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      count++;
      current = current->right;
    } else {
      Node* pre = current->left;
      while (pre->right != nullptr && pre->right != current) {
        pre = pre->right;
      }
      if (pre->right == nullptr) {
        pre->right = current;
        current = current->left;
      } else {
        pre->right = nullptr;
        count++;
        current = current->right;
      }
    }
  }
  std::cout << count << std::endl;
}

hard

A. This code correctly counts nodes using Morris traversal without extra space

B. Counting should be done only when pre->right is nullptr

C. Count variable must be global to work correctly

D. Morris traversal cannot be used to count nodes without recursion

Solution

1. Step 1: Understand counting during Morris traversal

   Count nodes when visiting them: when left is nullptr or after restoring links (pre->right == current).

2. Step 2: Verify code increments count correctly

   Code increments count in both cases correctly, so it counts all nodes without extra space or recursion.

3. Final Answer:

   This code correctly counts nodes using Morris traversal without extra space -> Option A

4. Quick Check:

   Count increments on node visit = correct [OK]

Hint: Increment count on node visit before moving right [OK]

Common Mistakes:

• Counting only once per node visit
• Making count global unnecessarily
• Assuming Morris can't count nodes