Morris Traversal Inorder Without Stack in DSA C++ - Time & Space Complexity

Time Complexity: Morris Traversal Inorder Without Stack

O(n)

Understanding Time Complexity

We want to understand how the Morris Traversal method processes a binary tree without using extra memory for a stack or recursion.

How does the number of steps grow as the tree size increases?

Scenario Under Consideration

Analyze the time complexity of the following Morris Inorder Traversal code.

void morrisInorder(Node* root) {
  Node* current = root;
  while (current != nullptr) {
    if (current->left == nullptr) {
      // Visit current node
      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;
        // Visit current node
        current = current->right;
      }
    }
  }
}
    

This code visits all nodes of a binary tree in inorder sequence without using a stack or recursion by temporarily modifying tree links.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer while loop visits each node, and the inner while loop finds the rightmost node in the left subtree.
• How many times: Each edge in the tree is visited at most twice, once to create a temporary link and once to remove it.

How Execution Grows With Input

As the number of nodes (n) grows, the traversal visits each node and its edges a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 visits (nodes and edges)
100	About 200 visits
1000	About 2000 visits

Pattern observation: The operations grow roughly twice the number of nodes, so growth is linear.

Final Time Complexity

Time Complexity: O(n)

This means the traversal time grows directly in proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "Because there is a nested loop, the time complexity must be quadratic O(n²)."

[OK] Correct: The inner loop does not run fully for every node; it only moves along edges that are visited twice, so total work stays linear.

Interview Connect

Understanding Morris Traversal shows you can optimize tree traversals by saving memory and still keep time efficient, a valuable skill for real-world coding.

Self-Check

"What if we used recursion instead of modifying links? How would the time and space complexity change?"

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