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

Time Complexity: Morris Traversal Inorder Without Stack

O(n)

Understanding Time Complexity

We want to understand how long Morris Traversal takes to visit all nodes in a binary tree without using extra memory for a stack.

How does the number of steps grow as the tree gets bigger?

Scenario Under Consideration

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

function morrisInorder(root) {
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      console.log(current.val);
      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;
        console.log(current.val);
        current = current.right;
      }
    }
  }
}
    

This code visits all nodes in a binary tree in order without using a stack or recursion by temporarily modifying the tree.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: Moving through nodes and finding the rightmost child (predecessor) 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 steps (each edge twice)
100	About 200 steps
1000	About 2000 steps

Pattern observation: The steps grow roughly twice the number of edges, so it grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

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

Interview Connect

Understanding Morris Traversal shows you can save memory by clever tree manipulation while keeping time efficient, a skill valued in real-world coding.

Self-Check

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