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?

Practice

1. What is the main advantage of Morris Traversal for inorder tree traversal compared to the traditional recursive or stack-based methods?

easy

A. It is faster than all other traversal methods.

B. It uses no extra space for stack or recursion.

C. It only works for binary search trees.

D. It modifies the tree permanently.

Solution

1. Step 1: Understand space usage in tree traversals

   Traditional inorder traversal uses recursion or a stack, which requires extra memory proportional to tree height.

2. Step 2: Morris Traversal space optimization

   Morris Traversal cleverly uses threaded binary trees to avoid stack or recursion, thus using O(1) extra space.

3. Final Answer:

   It uses no extra space for stack or recursion. -> Option B

4. Quick Check:

   Morris Traversal = O(1) space [OK]

Hint: Remember Morris uses tree links, no stack needed [OK]

Common Mistakes:

• Thinking Morris is faster in time complexity
• Believing Morris only works on BSTs
• Assuming Morris modifies tree permanently

2. Which of the following TypeScript code snippets correctly initializes the current node for Morris inorder traversal?

easy

A. let current: TreeNode | null = root;

B. let current = null;

C. let current: TreeNode = null;

D. let current: TreeNode = root.left;

Solution

1. Step 1: Identify correct initialization type

   We start traversal from the root node, so current should be root and allow null for empty trees.

2. Step 2: Check TypeScript syntax

   TypeScript requires correct type with possible null, so 'TreeNode | null' is correct.

3. Final Answer:

   let current: TreeNode | null = root; -> Option A

4. Quick Check:

   Correct type and initialization = let current: TreeNode | null = root; [OK]

Hint: Start traversal at root with nullable node type [OK]

Common Mistakes:

• Assigning null without type union
• Starting from root.left instead of root
• Using uninitialized or wrong type

3. Consider the following TypeScript code for Morris inorder traversal on this tree:

    2
   / \
  1   3

What will be the printed output sequence?

medium

A. [3, 2, 1]

B. [2, 1, 3]

C. [1, 2, 3]

D. [1, 3, 2]

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits left subtree, then node, then right subtree. For this tree, order is 1, 2, 3.

2. Step 2: Morris traversal mimics inorder without stack

   Morris traversal outputs nodes in inorder sequence, so output will be [1, 2, 3].

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Inorder of given tree = [1, 2, 3] [OK]

Hint: Inorder = left, root, right sequence [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Assuming Morris changes output order
• Mixing left and right subtree order

4. In this TypeScript snippet for Morris traversal, what is the bug?

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;
      // Missing console.log here
      current = current.right;
    }
  }
}

medium

A. Incorrect initialization of predecessor variable.

B. Using '===' instead of '==' in while condition.

C. Not updating current to current.left in else block.

D. Missing printing current.val before moving right after restoring link.

Solution

1. Step 1: Identify missing output in else block

   When restoring the tree link, the node's value must be printed before moving right, else node is skipped.

2. Step 2: Effect of missing print

   Without printing current.val in the unthreading step, nodes with left subtrees are skipped in the output, causing incomplete traversal results.

3. Final Answer:

   Missing printing current.val before moving right after restoring link. -> Option D

4. Quick Check:

   Missing console.log(current.val) in unthreading step causes skipped nodes [OK]

Hint: Print node value when restoring threaded link [OK]

Common Mistakes:

• Ignoring print statement placement
• Confusing predecessor initialization
• Thinking '===' causes infinite loop

5. Given a binary tree with nodes:

      4
     / \
    2   5
   / \
  1   3

Using Morris inorder traversal, what is the exact sequence of node values printed, and why does this method not use extra memory?

hard

A. [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion.

B. [4, 2, 1, 3, 5]; uses recursion internally.

C. [1, 3, 2, 4, 5]; uses a stack to track nodes.

D. [5, 4, 3, 2, 1]; modifies tree permanently.

Solution

1. Step 1: Determine inorder traversal sequence

   Inorder visits left subtree, node, right subtree. For this tree, sequence is 1, 2, 3, 4, 5.

2. Step 2: Explain Morris traversal memory usage

   Morris traversal creates temporary threaded links to predecessor nodes, avoiding stack or recursion, thus using O(1) extra space.

3. Final Answer:

   [1, 2, 3, 4, 5]; uses threaded links to avoid stack or recursion. -> Option A

4. Quick Check:

   Inorder = [1,2,3,4,5], O(1) space by threading [OK]

Hint: Inorder sequence + threaded links = no extra memory [OK]

Common Mistakes:

• Mixing traversal order
• Assuming recursion or stack used
• Believing tree is permanently changed