Morris Traversal Inorder Without Stack in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Morris Inorder Traversal on a Simple Tree

What is the output of the Morris inorder traversal on the following binary tree?

Tree structure:
2
/ \
1 3

Assume the traversal prints node values separated by spaces.

DSA Typescript

class Node {
  val: number;
  left: Node | null;
  right: Node | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function morrisInorder(root: Node | null): void {
  let current = root;
  while (current !== null) {
    if (current.left === null) {
      process.stdout.write(current.val + ' ');
      current = current.right;
    } else {
      let pre = current.left;
      while (pre.right !== null && pre.right !== current) {
        pre = pre.right;
      }
      if (pre.right === null) {
        pre.right = current;
        current = current.left;
      } else {
        pre.right = null;
        process.stdout.write(current.val + ' ');
        current = current.right;
      }
    }
  }
}

const root = new Node(2);
root.left = new Node(1);
root.right = new Node(3);
morrisInorder(root);

A 1 2 3

B 2 1 3

C 3 2 1

D 1 3 2

💡 Hint

Remember inorder traversal visits left subtree, then node, then right subtree.

Morris inorder traversal visits nodes in ascending order for BST. For the tree with root 2, left child 1, right child 3, the inorder sequence is 1 2 3.

🧠 Conceptual

intermediate

Understanding Thread Creation in Morris Traversal

In Morris inorder traversal, what is the purpose of creating a temporary thread (link) from the inorder predecessor to the current node?

A To permanently modify the tree structure for faster future traversals

B To avoid using recursion or stack by temporarily linking back to the current node after visiting left subtree

C To store node values in a separate array for output

D To mark nodes as visited to prevent revisiting

💡 Hint

Think about how Morris traversal avoids extra memory usage.

The temporary thread allows the traversal to return to the current node after finishing the left subtree without using stack or recursion. It is removed after use, so the tree remains unchanged.

🔧 Debug

advanced

Identify the Error in Modified Morris Traversal Code

What error will occur when running this modified Morris inorder traversal code snippet?

Code snippet:
let current = root;
while (current !== null) {
if (current.left !== null) {
let pre = current.left;
while (pre.right !== null && pre.right !== current) {
pre = pre.right;
}
if (pre.right === null) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
console.log(current.val);
current = current.right;
}
} else {
console.log(current.val);
current = current.right;
}
}

Note: The condition in the first if is reversed from standard Morris traversal.

A Infinite loop due to missing thread creation when left is null

B Correct output with no errors

C SyntaxError because of missing semicolons

D TypeError because current.left might be undefined

💡 Hint

Check what happens when current.left is null in this code.

The code only creates threads when current.left is not null, but the condition is reversed, so when current.left is null, it skips thread creation and can get stuck in an infinite loop.

📝 Syntax

advanced

Identify Syntax Error in Morris Traversal Implementation

Which option contains a syntax error that prevents the Morris inorder traversal code from running?

A if (pre.right === null) { pre.right = current; current = current.left; } else { pre.right = null; console.log(current.val); current = current.right; }

B while (pre.right !== null && pre.right !== current) pre = pre.right;

C class Node { val: number; left: Node | null; right: Node | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } }

D

let current = root
while (current !== null) { if (current.left === null) { console.log(current.val); current = current.right } else { let pre = current.left; while (pre.right !== null && pre.right !== current) { pre = pre.right } if (pre.right === null) { pre.right = current; current = current.left; } else { pre.right = null; console.log(current.val); current = current.right } } }

💡 Hint

Look for missing semicolons or braces in the code.

Option D is missing semicolons between statements inside the if block, causing syntax errors.

🚀 Application

expert

Number of Temporary Threads Created in Morris Traversal

Given a binary tree with 5 nodes arranged as:
4
/ \
2 5
/ \
1 3

How many temporary threads (links) will Morris inorder traversal create during the full traversal?

A 4

B 2

C 3

D 5

💡 Hint

Count how many nodes have a left child and thus create a thread to their inorder predecessor.

Threads are created for nodes with left children. Nodes 4 and 2 have left children, so threads are created for them. Node 2's left child 1 has no left child, so no thread. Total threads = 2 + 1 (for node 2's left subtree) = 3.

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