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

Time Complexity: Morris Traversal Inorder Without Stack

O(n)

Understanding Time Complexity

We want to understand how the Morris Traversal algorithm performs as the size of the tree grows.

Specifically, how many steps it takes to visit all nodes without using extra memory for a stack.

Scenario Under Consideration

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

function morrisInorder(root: TreeNode | null): void {
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      // Visit current node
      current = current.right;
    } else {
      let 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;
        // Visit current node
        current = current.right;
      }
    }
  }
}
    

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

Identify Repeating Operations

Look for loops and repeated steps in the code.

• Primary operation: The outer while loop runs once per node, moving through the tree.
• Inner loop: The inner while loop finds the rightmost node in the left subtree (predecessor) and can run multiple times per node.
• How many times: Each edge in the tree is visited at most twice due to temporary pointer changes.

How Execution Grows With Input

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

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

Pattern observation: The operations grow roughly linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the algorithm visits each node a constant number of times, so the total steps grow directly with the number of nodes.

Common Mistake

[X] Wrong: "The inner loop makes this algorithm slower than linear because it can run many times per node."

[OK] Correct: Each edge is visited at most twice due to temporary links, so the total work is still proportional to the number of nodes.

Interview Connect

Understanding Morris Traversal shows you can traverse trees efficiently without extra memory, a useful skill for optimizing space in interviews.

Self-Check

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