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?"