Why Morris Traversal Inorder Without Stack in DSA C++?

The Big Idea

Discover how to walk through a tree without carrying extra memory or getting lost!

The Scenario

Imagine you want to walk through a maze (a tree) and note down every room (node) you visit in order. Without a map or a helper (stack), you try to remember every turn you took. It quickly becomes confusing and you might get lost or repeat rooms.

The Problem

Using a stack or recursion to remember your path takes extra memory and can slow you down. If the maze is huge, carrying this memory is heavy and inefficient. Also, managing this memory manually can cause mistakes and crashes.

The Solution

Morris Traversal cleverly uses the maze itself to mark your path temporarily. It creates small shortcuts (temporary links) so you can walk through all rooms in order without extra memory. After visiting, it cleans up these shortcuts, leaving the maze unchanged.

Before vs After

✗ Before

void inorderTraversal(Node* root) {
    std::stack<Node*> nodeStack;
    Node* current = root;
    while (current != nullptr || !nodeStack.empty()) {
        while (current != nullptr) {
            nodeStack.push(current);
            current = current->left;
        }
        current = nodeStack.top();
        nodeStack.pop();
        std::cout << current->data << " ";
        current = current->right;
    }
}

✓ After

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

What It Enables

This method enables you to traverse a binary tree in order using only constant extra space, making it efficient for large trees or memory-limited environments.

Real Life Example

Think of exploring a large library where you want to read every book in order without carrying a big notebook or asking for help. Morris Traversal is like using bookmarks inside the books themselves to remember where you left off.

Key Takeaways

Morris Traversal avoids extra memory by temporarily modifying the tree.

It visits nodes in inorder sequence without stack or recursion.

After traversal, the tree structure is restored to original.

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